Approximability of sparse integer programs
From MaRDI portal
Publication:634673
DOI10.1007/S00453-010-9431-ZzbMATH Open1218.68198arXiv0904.0859OpenAlexW2062075466MaRDI QIDQ634673FDOQ634673
Authors: Juan-Miguel Gracia 
Publication date: 16 August 2011
Published in: Algorithmica (Search for Journal in Brave)
Abstract: The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx: Ax >= b, 0 <= x <= d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A, b, c, d are nonnegative.) For any k >= 2 and eps>0, if P != NP this ratio cannot be improved to k-1-eps, and under the unique games conjecture this ratio cannot be improved to k-eps. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx: Ax <= b, 0 <= x <= d} where A has at most k nonzeroes per column, we give a (2k^2+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A_{ij} is small compared to b_i. Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.
Full work available at URL: https://arxiv.org/abs/0904.0859
Recommendations
Cites Work
- Title not available (Why is that?)
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Geometric algorithms and combinatorial optimization
- A fast approximation algorithm for the multicovering problem
- An analysis of the greedy algorithm for the submodular set covering problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Integer Programming with a Fixed Number of Variables
- Title not available (Why is that?)
- Title not available (Why is that?)
- Non-approximability results for optimization problems on bounded degree instances
- Some optimal inapproximability results
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- A linear-time approximation algorithm for the weighted vertex cover problem
- Efficient algorithms for integer programs with two variables per constraint.
- Submodular Function Minimization under Covering Constraints
- On the complexity of approximating \(k\)-set packing
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- 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
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Primal-dual approximation algorithms for integral flow and multicut in 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
- Approximation algorithms for covering/packing integer programs
- An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- Multicommodity demand flow in a tree and packing integer programs
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- The Demand-Matching Problem
- Monotonizing linear programs with up to two nonzeroes per column
- On \(k\)-column sparse packing programs
- Approximability of Sparse Integer Programs
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Approximation and Online Algorithms
Cited In (30)
- Primal-dual algorithms for precedence constrained covering problems
- Primal beats dual on online packing LPs in the random-order model
- Title not available (Why is that?)
- Partial Resampling to Approximate Covering Integer Programs
- Approximating covering integer programs with multiplicity constraints
- Scheduling split intervals with non-uniform demands
- Primal-dual algorithms for precedence constrained covering problems
- Sparsity of integer solutions in the average case
- Rounding to an integral program
- Approximating sparse covering integer programs online
- Compact representation of near-optimal integer programming solutions
- Network pollution games
- On improved interval cover mechanisms for crowdsourcing markets
- Approximability of Sparse Integer Programs
- Approximation algorithms for covering/packing integer programs
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Approximation Bounds for Sparse Programs
- On approximating (sparse) covering integer programs
- Parameterized complexity of sparse linear complementarity problems
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Approximation of optima of integer programs of the packing—covering type
- Approximating integer programs with positive right-hand sides
- Iterative packing for demand and hypergraph matching
- Precedence-constrained covering problems with multiplicity constraints
- On column-restricted and priority covering integer programs
- Precedence-constrained covering problems with multiplicity constraints
- Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance
- Multicommodity flow in trees: packing via covering and iterated relaxation
This page was built for publication: Approximability of sparse integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634673)
