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
• On improved interval cover mechanisms for crowdsourcing markets
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Primal-dual algorithms for precedence constrained covering problems
• Constant factor approximation algorithm for weighted flow-time on a single machine in pseudopolynomial time
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Set cover problems with small neighborhood covers
• Improved algorithm for resource allocation problems
• Hallucination helps: energy efficient virtual circuit routing
• Approximate Deadline-Scheduling with Precedence Constraints
• Fair scheduling via iterative quasi-uniform sampling
• Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities
• On capacitated set cover problems
• Resource allocation problem under single resource assignment
• Fixed-parameter algorithms for unsplittable flow cover
• On interval and circular-arc covering problems
• Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems
• Multicommodity flow in trees: packing via covering and iterated relaxation
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Approximating covering integer programs with multiplicity constraints
• Approximating sparse covering integer programs online
• On the geometric priority set cover problem
• Demand hitting and covering of intervals

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)