Online constrained optimization with recourse

作者：Avitabile T; Mathieu C; Parkinson L^*

来源：Information Processing Letters, 2013, 113(3): 81-86.

DOI：10.1016/j.ipl.2012.09.011

• Online algorithms
• Approximation algorithms
• Maximum cut
• Bipartite matching
• Ad-auctions

We study online packing and covering problems, stated as zero-one linear programs. This class of problems includes maximum cut, bipartite matching, and set cover. In the packing problem, variables arrive in an online fashion. Upon arrival of v, the weight of v in the objective function and in any constraints involving v is revealed and the algorithm may update its solution. In the covering problem, constraints arrive in an online fashion. We allow the relaxation that the algorithm may change the value of each variable a constant number of times, k.
We give an algorithm for OnlinePacking(k) and prove that for any is an element of > 0, there exists some k equal to (O) over tilde (1/is an element of) such that the algorithm gives a (1 - is an element of) approximation for OnlinePacking(k). We then show near-tightness for several cases.
We also prove that no deterministic algorithm exists for OnlineCovering(k) that achieves a competitive ratio less than 3/2.

• 出版日期2013-2-15