Online Algorithms for Covering and Packing Problems with Convex Objectives
Authors:
- Yossi AzarYAYossi Azar
- Niv BuchbinderNBNiv Buchbinder
- T-H. Hubert ChanTCT-H. Hubert Chan
- Shahar ChenSCShahar Chen
- Ilan Reuven CohenICIlan Reuven Cohen
- Anupam GuptaAGAnupam Gupta
- Zhiyi HuangZHZhiyi Huang
- Ning KangNKNing Kang
- Viswanath NagarajanVNViswanath Nagarajan
- Joseph NaorJNJoseph Naor
- Debmalya PanigrahiDPDebmalya Panigrahi
Open Access
- 1 October 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 148-157
Abstract
We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min xϵ R + n f(x) s.t. Ax ≥ 1, where f:R + n → R + is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max yϵR+ m Σ j=1 m yj - g(A T y), where g:R + n →R + is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.Keywords
This publication has 26 references indexed in Scilit:
- Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms2013
- A Primal-Dual Randomized Algorithm for Weighted PagingJournal of the ACM, 2012
- Randomized Competitive Algorithms for Generalized CachingSIAM Journal on Computing, 2012
- Generalized Machine Activation Problems2011
- Energy Efficient Scheduling via Partial Shutdown2010
- Speed Scaling for Weighted Flow TimeSIAM Journal on Computing, 2010
- The Design of Competitive Online Algorithms via a Primal—Dual ApproachFoundations and Trends® in Theoretical Computer Science, 2009
- The Online Set Cover ProblemSIAM Journal on Computing, 2009
- A general approach to online network optimization problemsACM Transactions on Algorithms, 2006
- Estimation of moments of sums of independent real random variablesThe Annals of Probability, 1997