论文地址：https://theory.stanford.edu/~sergei/papers/ec10-lagrange.pdf
《具有预测的最优在线分配》总结
本文由Erik Vee、Sergei Vassilvitskii和Jayavel Shanmugasundaram撰写，主要研究了在线分配中具有预测的最优分配问题，提出了一种解决该问题的方法。
1. 引言
- 问题背景：在展示广告中，出版商面临用户访问与广告合同的分配问题，需满足供应和需求约束，并追求公平或代表性的分配。但传统方法存在图规模大、服务困难和鲁棒性问题。
- 问题定义：引入在线分配与预测问题，算法能获取未来到达顶点的样本，分为离线和在线两个阶段，通过采样图计算紧凑分配计划。
2. 背景和定义
- 一般框架：在线分配与预测问题是经典在线二分匹配问题的变体，允许指定额外线性约束，目标是最小化特定目标函数，可放松为分数分配，关键区别是算法可获得预测。
- 在线分配与预测：具体定义了分配问题中的图、节点、约束和目标函数，算法在预处理阶段根据预测图和目标函数生成分配计划，在线阶段根据分配计划进行分配。
- 在线预算投标者与预测：简要描述了该问题的设置，包括图、供应、预算、成本和约束等。
- 目标函数：目标函数需满足凸性、良态、可分离和尺度无关等性质，才能保证采样的适用性。
- 鲁棒性：通过增加需求来定义ε - 可行性和ε - 优性，以解决分配计划在预测图和供应下不一定能得到最优和可行解的问题。
3. 紧凑分配计划
- 存在性与性质：对于良构目标函数，存在连续函数˜x(α)，使得通过需求约束的对偶值可重构最优解，且该解具有鲁棒性，对预测中的小误差不敏感。
- 关键性质：函数˜x的关键性质是，若为图G和供应s、需求d找到最优解，扰动s为s′后，可微调d为d′使⟨G, s′, d′⟩的最优解与原最优解相同，且该性质对插值也适用。
4. 使用P的样本
- 采样方法：采用类似于Karp - Luby采样的重要性采样方法，根据概率选择供应节点创建样本集ˆI，定义ˆs和ˆd，得到采样后的问题ˆP。
- 定理证明：定理3表明，通过在对偶空间RJ中工作、分析函数˜x(α)的敏感性和证明采样对需求约束的扰动不大，可证明在采样后能以高概率得到接近最优的解。具体通过引理2、3、4的证明，最终完成定理3的证明。
5. 整体算法
将之前定理的结果整合为解决线性分配问题的简单算法，包括预处理阶段和在线阶段，算法具有高效性和接近最优的性质。
6. 结论
介绍了在线分配与预测问题，展示了对偶空间对创建分配计划和指导在线算法的作用，通过移动到对偶空间的子空间，创建了紧凑分配计划和鲁棒在线算法，在实际中有重要意义，能以接近最优的方式解决问题并进行分布式服务。
7. 参考文献
列出了相关的参考文献。