Approximation algorithms for covering/packing integer programs

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^Tx:[email protected]?Z"+^n,Ax>=a,Bx==a) and multiplicity constraints (x=

• Publication year

  2002

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2002-05-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcss.2005.05.002arXiv cs/0205030
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximating covering integer programs with multiplicity constraints

  2003cited by this paper
• Tight approximation results for general covering integer programs

  2001cited by this paper
• A constant-factor approximation algorithm for packet routing and balancing local vs

  2001cited by this paper
• Approximation algorithms for facility location problems

  2000cited by this paper
• Strengthening integrality gaps for capacitated network design and covering problems

  2000influential reference
• Improved Approximation Guarantees for Packing and Covering Integer Programs

  1999cited by this paper
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  1997cited by this paper
• A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria

  1997cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems

  1996cited by this paper
• An extension of the Lovász local lemma, and its applications to integer programming

  1996cited by this paper
• Randomized rounding without solving the linear program

  1995cited by this paper
• Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs

  1993cited by this paper
• Fast approximation algorithms for fractional packing and covering problems

  1991cited by this paper
• Optimal file sharing in distributed networks

  1991cited by this paper
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs

  1987cited by this paper
• Ten lectures on the probabilistic method

  1987cited by this paper
• Probabilistic construction of deterministic algorithms: Approximating packing integer programs

  1986cited by this paper
• Algorithmic theory of numbers, graphs and convexity

  1986cited by this paper
• On the greedy heuristic for continuous covering and packing problems

  1982cited by this paper
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

  1982cited by this paper
• A Greedy Heuristic for the Set-Covering Problem

  1979cited by this paper
• Facets of the knapsack polytope

  1975cited by this paper
• Facet of regular 0–1 polytopes

  1975cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Faces for a linear inequality in 0–1 variables

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• On a Combinatorial Game

  1973cited by this paper
• Greedy Heuristics for Integer Programming with Non-negative Data

  year unknowncited by this paper

• Minimal Actuator Selection

  2026cites this paper
• Approximating Electoral Control Problems

  2025influential citation
• On generalizations of partial scenario set cover

  2025cites this paper
• Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull

  2025cites this paper
• Covering a Few Submodular Constraints and Applications

  2025cites this paper
• Online Rounding for Set Cover under Subset Arrivals

  2025cites this paper
• Joint Controller Placement and TDMA Scheduling in Software Defined Wireless Multihop Networks

  2025cites this paper
• Online Multiset Submodular Cover

  2024cites this paper
• Bounding the Price-of-Fair-Sharing Using Knapsack-Cover Constraints to Guide Near-Optimal Cost-Recovery Algorithms

  2023influential citation
• Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs

  2023cites this paper
• When Computing Power Network Meets Distributed Machine Learning: An Efficient Federated Split Learning Framework

  2023cites this paper
• DATM: A Novel Data Agnostic Topic Modeling Technique With Improved Effectiveness for Both Short and Long Text

  2023cites this paper
• Precedence-constrained covering problems with multiplicity constraints

  2023cites this paper
• On Improved Interval Cover Mechanisms for Crowdsourcing Markets

  2022cites this paper
• Algorithms for covering multiple submodular constraints and applications

  2022cites this paper
• Annealed Training for Combinatorial Optimization on Graphs

  2022cites this paper
• Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions

  2022cites this paper
• Deterministic Massively Parallel Algorithms for Ruling Sets

  2022cites this paper
• Set Selection under Explorable Stochastic Uncertainty via Covering Techniques

  2022cites this paper
• Auditing for Core Stability in Participatory Budgeting

  2022cites this paper
• Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory

  2022cites this paper
• Optimizing Mobile Crowdsensing Platforms for Boundedly Rational Users

  2022cites this paper
• Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations

  2022cites this paper
• Safe Approximation - An Efficient Solution for a Hard Routing Problem

  2021cites this paper
• Modeling RIS Empowered Outdoor-to-Indoor Communication in mmWave Cellular Networks

  2021cites this paper
• CS 583: Approximation Algorithms

  2021cites this paper
• Randomized rounding algorithms for large scale unsplittable flow problems

  2021cites this paper
• Predictive Optimization with Zero-Shot Domain Adaptation

  2021cites this paper
• Improved Learning Rates for Stochastic Optimization: Two Theoretical Viewpoints

  2021cites this paper
• Greedy approaches to approximation of some NP-hard combinatorial optimization problems. (Approches gloutonnes pour l'approximation de problèmes combinatoires NP-difficiles)

  2020cites this paper
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

  2020cites this paper
• Predicting many properties of a quantum system from very few measurements

  2020cites this paper
• Fast LP-based Approximations for Geometric Packing and Covering Problems

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• A near-linear time minimum Steiner cut algorithm for planar graphs

  2019cites this paper
• D S ] 1 3 M ar 2 01 9 Stochastic Packing Integer Programs with Few Queries ∗

  2019cites this paper
• Towards Maximal Service Profit in Geo-Distributed Clouds

  2019cites this paper
• Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard

  2019cites this paper
• Virtual network embeddings: Theoretical foundations and provably good algorithms

  2019cites this paper
• Adaptive estimation of categorical data streams with applications in change detection and density estimation

  2019cites this paper
• On Approximating Partial Set Cover and Generalizations

  2019cites this paper
• The Problems of Selecting Problems

  2019cites this paper
• Fast approximations for combinatorial optimization via multiplicative weight updates

  2019influential citation
• A Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

  2018cites this paper
• Randomized MWU for Positive LPs

  2018influential citation
• D S ] 1 4 A pr 2 01 8 Partial resampling to approximate covering integer programs ∗

  2018cites this paper
• CS 583 : Approximation Algorithms : Covering Problems ∗

  2018cites this paper
• On the Optimality of Affine Policies for Budgeted Uncertainty Sets

  2018cites this paper
• 0 Mining Protein Interaction Groups

  2018cites this paper
• Finding Interesting Subgraphs with Guarantees

  2018cites this paper
• A Simple Approximation for a Hard Routing Problem

  2018cites this paper
• Automatic identification of optimal marker genes for phenotypic and taxonomic groups of microorganisms

  2018cites this paper
• Joint Placement and Routing of Network Function Chains in Data Centers

  2018cites this paper
• Algorithms and complexity results for packing and covering problems and robust dynamic network flows under primal-dual aspects

  2018cites this paper
• Fast, Deterministic and Sparse Dimensionality Reduction

  2018cites this paper
• Interference Statistics Approximations for Data Rate Analysis in Uplink Massive MTC

  2018cites this paper
• Using Activity Patterns to Place Electric Vehicle Charging Stations in Urban Regions

  2018influential citation
• Graph Scan Statistics With Uncertainty

  2018cites this paper
• Few Cuts Meet Many Point Sets

  2018cites this paper
• Resource allocation and decision making for groups

  2018cites this paper
• On Approximating (Sparse) Covering Integer Programs

  2018influential citation
• How to Make Envy Vanish Over Time

  2018cites this paper
• Probabilistic optimal solution assessment for DCOPs

  2018cites this paper
• Fast and Deterministic Approximations for k-Cut

  2018cites this paper
• , 1994-B 434 a BenApproximation algorithms for hub location problems /

  2018cites this paper
• On Simultaneous Two-player Combinatorial Auctions

  2017cites this paper
• De-anonymization of Social Networks with Communities: When Quantifications Meet Algorithms

  2017cites this paper
• Stochastic packing integer programs with few queries

  2017influential citation
• Modélisation graphique et simulation en traitement d'information quantique. (Graph modeling and simulation in quantum information processing)

  2017influential citation
• Scheduling Non-Preemptible Jobs to Minimize Peak Demand

  2017cites this paper
• Family-Personalized Dietary Planning with Temporal Dynamics

  2017influential citation
• Lower bounds and algorithms for the minimum cardinality bin covering problem

  2017cites this paper
• Local ratio method on partial set multi-cover

  2017cites this paper
• Feedback Acquisition and Reconstruction of Spectrum-Sparse Signals by Predictive Level Comparisons

  2017cites this paper
• Mixed Integer Programming with Convex/Concave Constraints: Fixed-Parameter Tractability and Applications to Multicovering and Voting

  2017cites this paper
• An improved approximation algorithm for the covering 0 – 1 integer program

  2017influential citation
• A pr 2 01 7 Partial resampling to approximate covering integer programs ∗

  2017influential citation
• Finding fixed point free elements and small bases in permutation groups

  2017cites this paper
• On mining approximate and exact fault-tolerant frequent itemsets

  2017cites this paper
• How to Generate Randomized Roundings with Dependencies and How to Derandomize Them

  2016cites this paper
• Detecting misinformation in online social networks before it is too late

  2016cites this paper
• Approximation algorithm for partial positive influence problem in social network

  2016cites this paper
• Minimizing the maximum flow time in batch scheduling

  2016cites this paper
• An exact algorithm for finding cancer driver somatic genome alterations: the weighted mutually exclusive maximum set cover problem

  2016cites this paper
• 44 RANDOMIZATION AND DERANDOMIZATION

  2016cites this paper
• Polynomial-time approximation for nonconvex optimization problems with an L1-constraint

  2016cites this paper
• Automatic media planning: Optimal advertisement placement problems

  2016cites this paper
• Local ratio method on partial set multi-cover

  2016cites this paper
• Disjoint Paths and Unsplittable Flow ( Version 2 . 7 )

  2016cites this paper
• Computing an Approximately Optimal Agreeable Set of Items

  2016cites this paper
• Toward Power-Efficient Backbone Routers

  2016cites this paper
• Medial Axis Based Routing Has Constant Load Balancing Factor

  2015cites this paper
• Derandomized Construction of Combinatorial Batch Codes

  2015cites this paper
• Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round

  2015cites this paper
• Partial resampling to approximate covering integer programs †

  2015cites this paper
• Approximate Deadline-Scheduling with Precedence Constraints

  2015cites this paper
• Approximation Algorithms for Single-Minded Pricing and Unique Coverage on Graphs and Geometric Objects

  2015cites this paper
• Approximability of Optimization Problems through Adiabatic Quantum Computation

  2014cites this paper
• Approximability of the robust representatives selection problem

  2014influential citation
• Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems

  2014cites this paper