### Abstract

We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Z^{n}_{≥}_{0} s.t. Ax ≥ b and x ≤ d; where A ∈ R^{m}_{≥}_{0}^{×n}, b ∈ R^{m}_{≥}0, and c, d ∈ R^{n}_{≥}_{0} all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP_{∞}. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP_{∞} in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP_{∞}.

Original language | English (US) |
---|---|

Pages | 1596-1615 |

Number of pages | 20 |

State | Published - Jan 1 2019 |

Event | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019 |

### Conference

Conference | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 |
---|---|

Country | United States |

City | San Diego |

Period | 1/6/19 → 1/9/19 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*On approximating (sparse) covering integer programs*. 1596-1615. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.

**On approximating (sparse) covering integer programs.** / Chekuri, Chandra Sekhar; Quanrud, Kent.

Research output: Contribution to conference › Paper

}

TY - CONF

T1 - On approximating (sparse) covering integer programs

AU - Chekuri, Chandra Sekhar

AU - Quanrud, Kent

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn≥0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm≥0×n, b ∈ Rm≥0, and c, d ∈ Rn≥0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.

AB - We consider approximation algorithms for covering integer programs of the form min hc, xi over x ∈ Zn≥0 s.t. Ax ≥ b and x ≤ d; where A ∈ Rm≥0×n, b ∈ Rm≥0, and c, d ∈ Rn≥0 all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x ≤ d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.

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

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

M3 - Paper

AN - SCOPUS:85065888064

SP - 1596

EP - 1615

ER -