Approximability of sparse integer programs
From MaRDI portal
Publication:634673
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
- A fast approximation algorithm for the multicovering problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Approximability of Sparse Integer Programs
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for covering/packing integer programs
- Approximation and Online Algorithms
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Efficient algorithms for integer programs with two variables per constraint.
- Geometric algorithms and combinatorial optimization
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Integer Programming with a Fixed Number of Variables
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Monotonizing linear programs with up to two nonzeroes per column
- Multicommodity demand flow in a tree and packing integer programs
- Non-approximability results for optimization problems on bounded degree instances
- On \(k\)-column sparse packing programs
- 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
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- On the complexity of approximating \(k\)-set packing
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Some optimal inapproximability results
- Submodular Function Minimization under Covering Constraints
- The Demand-Matching Problem
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(29)- Primal-dual algorithms for precedence constrained covering problems
- On improved interval cover mechanisms for crowdsourcing markets
- Primal-dual algorithms for precedence constrained covering problems
- Rounding to an integral program
- Approximation of optima of integer programs of the packing—covering type
- Precedence-constrained covering problems with multiplicity constraints
- On column-restricted and priority covering integer programs
- Iterative packing for demand and hypergraph matching
- Precedence-constrained covering problems with multiplicity constraints
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- Approximation Bounds for Sparse Programs
- Parameterized complexity of sparse linear complementarity problems
- Approximation algorithms for covering/packing integer programs
- Primal beats dual on online packing LPs in the random-order model
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Approximability of Sparse Integer Programs
- Sparsity of integer solutions in the average case
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Approximating covering integer programs with multiplicity constraints
- Approximating integer programs with positive right-hand sides
- Scheduling split intervals with non-uniform demands
- Approximating sparse covering integer programs online
- Network pollution games
- On approximating (sparse) covering integer programs
- Compact representation of near-optimal integer programming solutions
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
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)
