Online constrained optimization with recourse

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 ϵ>0ϵ>0, there exists some k   equal to O˜(1/ϵ) such that the algorithm gives a (1−ϵ)(1−ϵ) 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.

► We suggest a model for online packing and covering that allows recourse.
► We show that recourse improves the achievable competitive ratio for online packing.
► We show the near-tightness of the result for several problems.
► We show that the same technique (or any other deterministic algorithm) is not effective for online covering with recourse.