\(\ell_1\)-sparsity approximation bounds for packing integer programs
From MaRDI portal
Publication:5918913
DOI10.1007/s10107-020-01472-7zbMath1453.90102arXiv1902.08698OpenAlexW3005877089MaRDI QIDQ5918913
Kent Quanrud, Chandra Chekuri, Manuel Torres
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.08698
Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the discrepancy of matrices with bounded row and column sums
- Approximability of sparse integer programs
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the complexity of approximating \(k\)-set packing
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Approximability of Sparse Integer Programs
- Partial Resampling to Approximate Covering Integer Programs
- On Multidimensional Packing Problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Constrained Submodular Maximization via a Nonsymmetric Technique
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Non-approximability results for optimization problems on bounded degree instances
- On Approximating (Sparse) Covering Integer Programs
- Probability and Computing
- A Unified Continuous Greedy Algorithm for Submodular Maximization
This page was built for publication: \(\ell_1\)-sparsity approximation bounds for packing integer programs
