Approximation algorithms for covering/packing integer programs
From MaRDI portal
(Redirected from Publication:2575835)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 871894 (Why is no real title available?)
- scientific article; zbMATH DE number 910872 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
- Approximating covering integer programs with multiplicity constraints
- Approximation algorithms for combinatorial problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- On a combinatorial game
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- On the ratio of optimal integral and fractional covers
- Optimal File Sharing in Distributed Networks
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
Cited in
(56)- Approximability of sparse integer programs
- 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
- An approximation algorithm for the partial covering 0-1 integer program
- Approximating covering integer programs with multiplicity constraints
- Algorithms for covering multiple submodular constraints and applications
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
- scientific article; zbMATH DE number 2081015 (Why is no real title available?)
- Online multiset submodular cover
- New approaches to covering and packing problems
- Approximating sparse covering integer programs online
- Packing and covering with linear programming: a survey
- Lower bounds and algorithms for the minimum cardinality bin covering problem
- scientific article; zbMATH DE number 7040611 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 1830719 (Why is no real title available?)
- Approximate Deadline-Scheduling with Precedence Constraints
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- scientific article; zbMATH DE number 2163022 (Why is no real title available?)
- Set selection under explorable stochastic uncertainty via covering techniques
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- Approximation algorithms for integer covering problems via greedy column generation
- Cover and pack inequalities for (mixed) integer programming
- On approximating (sparse) covering integer programs
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- An improved approximation algorithm for the covering 0-1 integer program
- \(\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
- Stochastic packing integer programs with few queries
- Precedence-constrained covering problems with multiplicity constraints
- 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 algorithm for partial positive influence problem in social network
- Approximating disjoint-path problems using packing integer programs
- Mobile facility location: combinatorial filtering via weighted occupancy
- Approximation Schemes for Covering and Packing
- 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
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations
- Fast and deterministic approximations for \(k\)-cut
- 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)
