Approximability of sparse integer programs
From MaRDI portal
Publication:634673
DOI10.1007/s00453-010-9431-zzbMath1218.68198arXiv0904.0859OpenAlexW2062075466MaRDI QIDQ634673
Publication date: 16 August 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0904.0859
Related Items (13)
Primal-Dual Algorithms for Precedence Constrained Covering Problems ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Scheduling split intervals with non-uniform demands ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ Network pollution games ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Precedence-constrained covering problems with multiplicity constraints ⋮ Approximating Sparse Covering Integer Programs Online ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Precedence-constrained covering problems with multiplicity constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- A fast approximation algorithm for the multicovering problem
- Geometric algorithms and combinatorial optimization
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Monotonizing linear programs with up to two nonzeroes per column
- An analysis of the greedy algorithm for the submodular set covering problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the complexity of approximating \(k\)-set packing
- Approximation algorithms for covering/packing integer programs
- Integer Programming with a Fixed Number of Variables
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- On k-Column Sparse Packing Programs
- Multicommodity demand flow in a tree and packing integer programs
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Approximability of Sparse Integer Programs
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Submodular Function Minimization under Covering Constraints
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Non-approximability results for optimization problems on bounded degree instances
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- The Demand-Matching Problem
- Some optimal inapproximability results
- Approximation and Online Algorithms
- Efficient algorithms for integer programs with two variables per constraint.
This page was built for publication: Approximability of sparse integer programs
