Mathematics of Operations Research · 2009 · 201 citations · 29 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsCombinatorial OptimizationDiscrete OptimizationInteger ProgrammingLinear ProgrammingOnline AlgorithmsConstraintsLinear ConstraintsLinear Cost FunctionsOnline PackingPackingPacking ProblemsPrimal-dual AlgorithmsPrimal-dual Online Algorithms
Online covering and packing problems reveal constraints or profit functions incrementally, requiring algorithms to maintain feasible, monotone solutions at every round. The study introduces deterministic primal‑dual algorithms for a wide range of online fractional and integral covering and packing problems. The authors develop novel online primal‑dual techniques that process new variables each round and analyze them via competitive analysis. These algorithms achieve provable competitive ratios within the online primal‑dual framework.
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 fractional covering and packing problems. We also provide deterministic algorithms for several integral online covering and packing problems. Our algorithms are designed via a novel online primal-dual technique and are evaluated via competitive analysis.
29
An optimal algorithm for on-line bipartite matching
Richard M. Karp, Umesh Vazirani, Vijay V. Vazirani · 1990 · 724 citations · Full text
AdWords and generalized online matching
Aranyak Mehta, Amin Saberi, Umesh Vazirani et al. · Journal of the ACM · 2007 · 622 citations