On Approximating (Sparse) Covering Integer Programs

DOI10.1137/1.9781611975482.97zbMath1431.68149arXiv1807.11538OpenAlexW2949505842MaRDI QIDQ5236281

Kent Quanrud, Chandra Chekuri

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

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

Related Items (8)

Algorithms for covering multiple submodular constraints and applications ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Approximation of set multi-cover via hypergraph matching ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs

This page was built for publication: On Approximating (Sparse) Covering Integer Programs