## Abstract

We consider the following semi-infinite linear programming problems: max (resp., min) c ^{T} x s.t. yTAix+(di)Tx≤bi (resp., yTAix+(di)Tx≥bi), for all y∈ Y _{i} , for i= 1 , … , N, where Yi⊆R+m are given compact convex sets and Ai∈R+mi×n, b=(b1,…bN)∈R+N, di∈R+n, and c∈R+n 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 Y _{i} , and the goal is to optimize the objective function for the worst case choice in each Y _{i} . When the uncertainty sets Y _{i} 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 Y _{i} are simple, such as ellipsoids or boxes, this yields substantial improvements in running time over general convex programming solvers. We also consider the mixed packing/covering problem, in which both packing and covering constraints are given, and the objective is to find an approximately feasible solution.

Original language | British English |
---|---|

Pages (from-to) | 2377-2429 |

Number of pages | 53 |

Journal | Algorithmica (New York) |

Volume | 81 |

Issue number | 6 |

DOIs | |

State | Published - 1 Jun 2019 |

## Keywords

- Multiplicative weights update
- Packing and covering
- Robust optimization
- Second-order cone programming