【论文评述】The Design of Competitive Online Algorithms via a Primal–Dual Approach

文献：Buchbinder N, Naor J S. The design of competitive online algorithms via a primal–dual approach[J]. Foundations and Trends® in Theoretical Computer Science, 2009, 3(2–3): 93-263.

---

基础知识

前面一部分感觉公式太多了，用markdown有点麻烦，当时做笔记时直接截图写在了本地的word上。这里直接贴出来：

滑雪租聘问题

滑雪租聘问题：假如说我要滑雪，滑雪板可以租聘也可以直接购买，租聘一次的价格为，购买的价格为，但我不知道我这辈子要滑几次。请问我该如何设计我的花钱策略，使得不论我事实上最后要滑几次，我的开销都不与最低金额的比永远不可能超过一个足够小的常数。

这个问题-competitive的基本策略已经属于常识，那就是一直租聘，直到在租聘费用即将超过购买费用时，不再租聘，而是选择购买。

但是如果引入随机化，可以做到-competitive。

如何通过primal-dual方法得到上面这两个竞争系数呢？

首先，要把这个问题变成线性规划问题。

首先考虑滑雪租聘问题的离线版本（也就是开天眼，一开始就知道这辈子要滑几次雪），它是非常简单的（但这个形式化是有用的）。

设为是否已购买的标志变量，为第天是否租聘的标志变量，整数规划为：

对于任意天数：

暂时放松这个问题，允许。则我们有对偶和原始规划为：

（对照着前面的primal-dual的式子形式就可以写出来）

在线确定型算法的-competitive可以用下面的方法得到：

在第天，如果约束条件已被满足，则什么都不做；若尚未被满足，则把连续增加直到Dual中的某个约束条件变紧，然后将这个约束条件对应的Primal中的变量设为。

最后，可以发现：

若，则；

若，则；

若，则。

根据近似互补松弛定理，这个算法是-competitive的。

在线随机算法则如下所示：

相关竞争系数直接看论文吧，不写了，最后用的是弱对偶性原理。

所以总之我们可以看到，Primal-Dual总体上就是两边一起搞搞，两边都搞出可行解，并且能够找到可以用得上弱对偶性或者近似互补松弛的关系。

(东西太多了，先不写啦！)