On column-restricted and priority covering integer programs

DOI10.1007/978-3-642-13036-6_27zbMATH Open1285.90014arXiv1003.1507OpenAlexW1574334008MaRDI QIDQ3569830FDOQ3569830

Authors: Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann 

Publication date: 22 June 2010

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: In a column-restricted covering integer program (CCIP), all the non-zero entries of any column of the constraint matrix are equal. Such programs capture capacitated versions of covering problems. In this paper, we study the approximability of CCIPs, in particular, their relation to the integrality gaps of the underlying 0,1-CIP. If the underlying 0,1-CIP has an integrality gap O(gamma), and assuming that the integrality gap of the priority version of the 0,1-CIP is O(omega), we give a factor O(gamma + omega) approximation algorithm for the CCIP. Priority versions of 0,1-CIPs (PCIPs) naturally capture quality of service type constraints in a covering problem. We investigate priority versions of the line (PLC) and the (rooted) tree cover (PTC) problems. Apart from being natural objects to study, these problems fall in a class of fundamental geometric covering problems. We bound the integrality of certain classes of this PCIP by a constant. Algorithmically, we give a polytime exact algorithm for PLC, show that the PTC problem is APX-hard, and give a factor 2-approximation algorithm for it.

Full work available at URL: https://arxiv.org/abs/1003.1507

Recommendations

• Approximating covering integer programs with multiplicity constraints
• Approximation algorithms for covering/packing integer programs
• An approximation algorithm for the partial covering 0-1 integer program
• Approximability of sparse integer programs
• Publication:4952606

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Integer programming (90C10)

Cited In (25)

• Primal-dual algorithms for precedence constrained covering problems
• Set cover problems with small neighborhood covers
• Approximating covering integer programs with multiplicity constraints
• Primal-dual algorithms for precedence constrained covering problems
• Resource allocation problem under single resource assignment
• Approximating sparse covering integer programs online
• On the geometric priority set cover problem
• Demand hitting and covering of intervals
• On improved interval cover mechanisms for crowdsourcing markets
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• Approximate Deadline-Scheduling with Precedence Constraints
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• On capacitated set cover problems
• Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• On interval and circular-arc covering problems
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• Hallucination Helps: Energy Efficient Virtual Circuit Routing
• Fixed-parameter algorithms for unsplittable flow cover
• Fair Scheduling via Iterative Quasi-Uniform Sampling
• Improved algorithm for resource allocation problems
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: On column-restricted and priority covering integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569830)