Partial Resampling to Approximate Covering Integer Programs
From MaRDI portal
Publication:4575724
DOI10.1137/1.9781611974331.ch139zbMath1423.90147arXiv1507.07402OpenAlexW2244411750MaRDI QIDQ4575724
Antares Chen, Aravind Srinivasan, David G. Harris
Publication date: 16 July 2018
Published in: Random Structures & Algorithms, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.07402
Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (4)
Algorithms for covering multiple submodular constraints and applications ⋮ Unnamed Item ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the discrepancy of matrices with bounded row and column sums
- Approximation hardness of dominating set problems in bounded degree graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximation algorithms for covering/packing integer programs
- New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning
- A threshold of ln n for approximating set cover
- An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- A constructive proof of the general lovász local lemma
- A Greedy Heuristic for the Set-Covering Problem
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Improved lower bounds on k‐independence
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- A Tight Analysis of the Greedy Algorithm for Set Cover
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Lopsidependency in the Moser-Tardos Framework
- Reducibility among Combinatorial Problems
- Non-approximability results for optimization problems on bounded degree instances
- The Moser--Tardos Framework with Partial Resampling
- On Approximating (Sparse) Covering Integer Programs
This page was built for publication: Partial Resampling to Approximate Covering Integer Programs
