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

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

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
• scientific article; zbMATH DE number 1445293

Cited in

(24)

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

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)