Article ID: | iaor200968814 |
Country: | United States |
Volume: | 34 |
Issue: | 2 |
Start Page Number: | 270 |
End Page Number: | 286 |
Publication Date: | May 2009 |
Journal: | Mathematics of Operations Research |
Authors: | Naor Joseph (Seffi), Buchbinder Niv |
Keywords: | programming: linear |
We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorithm needs to maintain a feasible solution in each round; in addition, the solutions generated over the different rounds need to satisfy a monotonicity property. We provide general deterministic primal-dual algorithms for online