TY - GEN
T1 - Online Algorithms for Covering and Packing Problems with Convex Objectives
AU - Azar, Yossi
AU - Buchbinder, Niv
AU - Chan, T. H.Hubert
AU - Chen, Shahar
AU - Cohen, Ilan Reuven
AU - Gupta, Anupam
AU - Huang, Zhiyi
AU - Kang, Ning
AU - Nagarajan, Viswanath
AU - Naor, Joseph
AU - Panigrahi, Debmalya
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/14
Y1 - 2016/12/14
N2 - We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxαRn+f(x) s.t. Ax ≥ 1, where f:Rn+ → 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: maxyαRm+ Σ mj=1 yj - g(AT y), where g:Rn+→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.
AB - We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxαRn+f(x) s.t. Ax ≥ 1, where f:Rn+ → 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: maxyαRm+ Σ mj=1 yj - g(AT y), where g:Rn+→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.
KW - Convex optimization
KW - Online algorithm
KW - Primal-dual algorithm
UR - http://www.scopus.com/inward/record.url?scp=85009351783&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85009351783&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2016.24
DO - 10.1109/FOCS.2016.24
M3 - Conference contribution
AN - SCOPUS:85009351783
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 148
EP - 157
BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PB - IEEE Computer Society
T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Y2 - 9 October 2016 through 11 October 2016
ER -