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 -