2014/12/29 by Buchbinder, Niv, Chen, Shahar, Gupta, Anupam +3
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1412.8347
We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve min \f(x) | Ax≥ 1, x≥ 0\, where the objective function f:ℝn→ ℝ is convex, and the constraint matrix Am× n is non-negative. The rows of A arrive online over time, and we wish to maintain a feasible solution x at all times while only increasing coordinates of x. We also consider "dual" packing problems of the form max \c^\intercal y - g(μ) | A^\intercal y ≤ μ, y≥ 0\, where g is a convex function. In the online setting, variables y and columns of A^\intercal arrive over time, and we wish to maintain a non-decreasing solution (y,μ). We provide an online primal-dual framework for both classes of problems with competitive ratio depending on certain "monotonicity" and "smoothness" parameters of f; our results match or improve on guarantees for some special classes of functions f considered previously. Using this fractional solver with problem-dependent randomized rounding procedures, we obtain competitive algorithms for the following problems: online covering LPs minimizing ℓp-norms of arbitrary packing constraints, set cover with multiple cost functions, capacity constrained facility location, capacitated multicast problem, set cover with set requests, and profit maximization with non-separable production costs. Some of these results are new and others provide a unified view of previous results, with matching or slightly worse competitive ratios.