论文 | A Dynamic Near - Optimal Algorithm for Online Linear Programming

论文地址

https://arxiv.org/pdf/0911.2974

总结

《A Dynamic Near - Optimal Algorithm for Online Linear Programming》 作者为Shipra Agrawal、Zizhuo Wang和Yinyu Ye，该论文提出了一种用于解决在线线性规划问题的近最优算法。

研究背景和意义：

• 在线优化在计算机科学、运筹学和管理科学等领域日益受到关注，许多实际问题可归结为在线线性规划问题。
• 随机置换模型在在线问题研究中被广泛采用，介于最坏情况分析和假设输入分布已知之间。

关键思路和主要结果：

• 算法：提出基于动态学习的算法，通过几何时间间隔动态更新阈值价格向量，根据之前揭示列学习到的对偶价格来确定当前时期的顺序决策。
• 结果1：对于在线线性规划问题（2），在随机置换模型下，对于满足$B = \min_{i}b_{i} \geq \Omega(\frac{m\log(n/\epsilon)}{\epsilon^{2}})$的所有输入，在线算法具有$1 - O(\epsilon)$的竞争力（定理1）。
• 结果2：对于在线线性规划问题（2），任何算法在$B = \min_{i}b_{i} \leq \frac{\log(m)}{\epsilon^{2}}$时，竞争力小于$1 - \Omega(\epsilon)$（定理2），即该条件对于获得近最优解是必要的。
• 结果3：将结果扩展到更一般的在线线性规划问题（3），在满足$B = \min_{i}b_{i} \geq \Omega(\frac{m\log(nk/\epsilon)}{\epsilon^{2}})$的条件下，算法具有$1 - O(\epsilon)$的竞争力（定理3）。

相关工作：

• 各种在线算法在随机置换模型下被研究，包括秘书问题、在线匹配和广告关键词问题、在线装箱问题等，本文的工作属于在该模型下研究算法性能的类别。
• 与其他工作相比，本文的算法具有动态学习能力，不依赖于输入分布的知识，通过动态更新价格提高了性能，明确了更新价格的最佳频率，提供了非平凡的下界，并应用了PAC - learning中的标准技术。

算法具体内容：

• 一次学习算法（OLA）：基于前$\epsilon n$个输入学习对偶价格向量，然后在剩余时间使用该对偶价格决定当前分配，该算法要求解决一个定义在$\epsilon n$个变量上的小线性规划。在满足$B = \min_{i}b_{i} \geq \frac{6m\log(n/\epsilon)}{\epsilon^{3}}$的条件下，该算法具有$1 - 6\epsilon$的竞争力（命题1）。
• 动态学习算法（DLA）：每当前沿历史加倍时（即时间$t = \epsilon n, 2\epsilon n, 4\epsilon n,\cdots$）更新价格，通过更仔细地选择数字$h_{\ell}$，在证明相同竞争力时对$B$的下界要求更弱。在满足$B = \min_{i}b_{i} \geq \frac{10m\log(n/\epsilon)}{\epsilon^{2}}$的条件下，该算法实现了定理1中的结果。

扩展内容：

• 在线多维线性规划：考虑多维决策的更一般在线线性规划，算法基本相同，通过引理8和9，定理3的证明与定理1类似。
• 在线整数规划：由于算法总是输出整数解，且竞争力分析是与相应线性规划松弛的最优解比较，所以定理1中声明的竞争力比率也适用于在线整数规划。
• 快速解决大线性规划的列采样：该算法可应用于解决过大的（离线）线性规划，通过随机采样减少变量，与列生成方法相似，本文提供了对这种方法近似程度的首次严格分析。

结论和未来研究方向：

• 提供了在随机到达顺序和一些关于右侧输入的温和条件下，具有$1 - O(\epsilon)$竞争力的算法，条件独立于最优目标值、目标系数和输入数据的分布。
• 未来研究方向包括探究当前对右侧输入$B$的大小限制是否紧密，填补算法与下界之间的差距是一个有趣的研究方向。