On column-restricted and priority covering integer programs

DOI10.1007/978-3-642-13036-6_27MaRDI QIDQ3569830zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(24)

• 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
• Hallucination helps: energy efficient virtual circuit routing
• Approximating sparse covering integer programs online
• Demand hitting and covering of intervals
• On the geometric priority set cover problem
• On improved interval cover mechanisms for crowdsourcing markets
• Approximate Deadline-Scheduling with Precedence Constraints
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities
• 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
• Fair scheduling via iterative quasi-uniform sampling
• On capacitated set cover problems
• Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
• On interval and circular-arc covering problems
• Fixed-parameter algorithms for unsplittable flow cover
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• 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)