On approximating (sparse) covering integer programs

DOI10.1137/1.9781611975482.97MaRDI QIDQ5236281zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kent Quanrud

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.11538

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Integer programming (90C10)

Abstract: We consider approximation algorithms for covering integer programs of the form min $langlec,xangle$ over $xinmathbb{N}^n$ subject to $Axgeqb$ and $xleqd$; where $Ainmathbb{R}_{geq0}^{mimesn}$, $binmathbb{R}_{geq0}^m$, and $c,dinmathbb{R}_{geq0}^n$ all have nonnegative entries. We refer to this problem as $operatornameCIP$, and the special case without the multiplicity constraints $xled$ as $operatorname{CIP}_{infty}$. 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 $operatornameCIP$ and $operatorname{CIP}_{infty}$ 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 [12] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for $operatornameCIP$ are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5,24,12]. 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]. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for $operatornameCIP$ and $operatorname{CIP}_{infty}$.

Recommendations

• Approximation algorithms for covering/packing integer programs
• Approximating sparse covering integer programs online
• Approximating sparse covering integer programs online
• Approximating covering integer programs with multiplicity constraints
• Approximability of sparse integer programs

Cited in

(20)

• Approximating covering integer programs with multiplicity constraints
• Algorithms for covering multiple submodular constraints and applications
• Approximation of set multi-cover via hypergraph matching
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• An approximation algorithm for the partial covering 0-1 integer program
• Approximation algorithms for covering/packing integer programs
• Approximating sparse covering integer programs online
• Approximability of Sparse Integer Programs
• An improved approximation algorithm for the covering 0-1 integer program
• Approximation Bounds for Sparse Programs
• Fast and deterministic approximations for \(k\)-cut
• Approximating sparse covering integer programs online
• Approximation and Online Algorithms
• Fast and Deterministic Approximations for k-Cut.
• \(\ell_1\)-sparsity approximation bounds for packing integer programs
• A parameterized approximation scheme for generalized partial vertex cover
• Approximability of sparse integer programs
• Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
• On generalizations of partial scenario set cover
• Bounding the price-of-fair-sharing using knapsack-cover constraints to guide near-optimal cost-recovery algorithms

This page was built for publication: On approximating (sparse) covering integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236281)