Approximation algorithms for covering/packing integer programs
From MaRDI portal
Publication:2575835
DOI10.1016/J.JCSS.2005.05.002zbMATH Open1082.68128arXivcs/0205030OpenAlexW1976432206MaRDI QIDQ2575835FDOQ2575835
Authors: Stavros G. Kolliopoulos, Neal E. Young 
Publication date: 7 December 2005
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Abstract: Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing min {c.x: x in Z^n_+, Ax > a, Bx < b, x < d}. We give a bicriteria-approximation algorithm that, given epsilon in (0, 1], finds a solution of cost O(ln(m)/epsilon^2) times optimal, meeting the covering constraints (Ax > a) and multiplicity constraints (x < d), and satisfying Bx < (1 + epsilon)b + beta, where beta is the vector of row sums beta_i = sum_j B_ij. Here m denotes the number of rows of A. This gives an O(ln m)-approximation algorithm for CIP -- minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx < b. The previous best approximation ratio has been O(ln(max_j sum_i A_ij)) since 1982. CIP contains the set cover problem as a special case, so O(ln m)-approximation is the best possible unless P=NP.
Full work available at URL: https://arxiv.org/abs/cs/0205030
Recommendations
Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Integer programming (90C10)
Cites Work
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the ratio of optimal integral and fractional covers
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Title not available (Why is that?)
- Title not available (Why is that?)
- On a combinatorial game
- Title not available (Why is that?)
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Title not available (Why is that?)
- Optimal File Sharing in Distributed Networks
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Approximating covering integer programs with multiplicity constraints
- A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
Cited In (56)
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Approximability of sparse integer programs
- An approximation algorithm for the partial covering 0-1 integer program
- Title not available (Why is that?)
- Algorithms for covering multiple submodular constraints and applications
- Approximating covering integer programs with multiplicity constraints
- Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
- Title not available (Why is that?)
- Online multiset submodular cover
- Approximating sparse covering integer programs online
- New approaches to covering and packing problems
- Packing and covering with linear programming: a survey
- Title not available (Why is that?)
- Lower bounds and algorithms for the minimum cardinality bin covering problem
- On improved interval cover mechanisms for crowdsourcing markets
- Auditing for core stability in participatory budgeting
- Approximability of Sparse Integer Programs
- Local ratio method on partial set multi-cover
- Monotone covering problems with an additional covering constraint
- Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
- Title not available (Why is that?)
- Approximate Deadline-Scheduling with Precedence Constraints
- Set selection under explorable stochastic uncertainty via covering techniques
- Title not available (Why is that?)
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- Approximation algorithms for integer covering problems via greedy column generation
- On approximating (sparse) covering integer programs
- An improved approximation algorithm for the covering 0-1 integer program
- Cover and pack inequalities for (mixed) integer programming
- Title not available (Why is that?)
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Approximate fixed-rank closures of covering problems
- Primal-dual approximation algorithms for a packing-covering pair of problems
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Fast and Deterministic Approximations for k-Cut.
- Approximation and Online Algorithms
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- Precedence-constrained covering problems with multiplicity constraints
- Stochastic packing integer programs with few queries
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Distributed algorithms for covering, packing and maximum weighted matching
- Approximation Schemes for Covering and Packing
- Approximation algorithm for partial positive influence problem in social network
- Mobile facility location: combinatorial filtering via weighted occupancy
- Approximating disjoint-path problems using packing integer programs
- On column-restricted and priority covering integer programs
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- Precedence-constrained covering problems with multiplicity constraints
- Few cuts meet many point sets
- Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- Computing a small agreeable set of indivisible items
This page was built for publication: Approximation algorithms for covering/packing integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575835)
