TY - GEN

T1 - A multiplicative weights update algorithm for packing and covering semi-infinite linear programs

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

AU - Najy, Waleed

N1 - Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We consider the following semi-infinite linear programming problems: max (resp., min) cT x s.t. yT Aix + (di)Tx ≤ bi (resp., yT Aix + (di)T x ≥ bi), for all y ∈ Yi, for i = 1, …, N, where Yi ⊆ ℝ+mi + are given compact convex sets and Ai ∈ ℝ+mi×n +, b = (b1, …, bN) ∈ ℝN+, di ∈ ℝn+, and c ∈ Rn + are given non-negative matrices and vectors. This general framework is useful in modeling many interesting problems. For example, it can be used to represent a sub-class of Robust optimization in which the coefficients of the constraints are drawn from convex uncertainty sets Yi, and the goal is to optimize the objective function for the worst-case choice in each Yi. When the uncertainty sets Yi are ellipsoids, we obtain a sub-class of Second-Order Cone Programming. We show how to extend the multiplicative weights update method to derive approximation schemes for the above packing and covering problems. When the sets Yi are simple, such as ellipsoids or boxes, this yields substantial improvements in the running time over general convex programming solvers.

AB - We consider the following semi-infinite linear programming problems: max (resp., min) cT x s.t. yT Aix + (di)Tx ≤ bi (resp., yT Aix + (di)T x ≥ bi), for all y ∈ Yi, for i = 1, …, N, where Yi ⊆ ℝ+mi + are given compact convex sets and Ai ∈ ℝ+mi×n +, b = (b1, …, bN) ∈ ℝN+, di ∈ ℝn+, and c ∈ Rn + are given non-negative matrices and vectors. This general framework is useful in modeling many interesting problems. For example, it can be used to represent a sub-class of Robust optimization in which the coefficients of the constraints are drawn from convex uncertainty sets Yi, and the goal is to optimize the objective function for the worst-case choice in each Yi. When the uncertainty sets Yi are ellipsoids, we obtain a sub-class of Second-Order Cone Programming. We show how to extend the multiplicative weights update method to derive approximation schemes for the above packing and covering problems. When the sets Yi are simple, such as ellipsoids or boxes, this yields substantial improvements in the running time over general convex programming solvers.

KW - Multiplicative weights update

KW - Packing and covering

KW - Robust optimization

KW - Second-order cone programming

UR - http://www.scopus.com/inward/record.url?scp=85010637381&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51741-4_7

DO - 10.1007/978-3-319-51741-4_7

M3 - Conference contribution

AN - SCOPUS:85010637381

SN - 9783319517407

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 91

BT - Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers

A2 - Mastrolilli, Monaldo

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - 14th International Workshop on Approximation and Online Algorithms, WAOA 2016

Y2 - 25 August 2016 through 26 August 2016

ER -