On Column-Restricted and Priority Covering Integer Programs

DOI10.1007/978-3-642-13036-6_27zbMath1285.90014arXiv1003.1507OpenAlexW1574334008MaRDI QIDQ3569830

Jochen Könemann, Deeparnab Chakrabarty, Elyot Grant

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

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

Related Items (21)

Approximate Deadline-Scheduling with Precedence Constraints ⋮ Resource allocation problem under single resource assignment ⋮ 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 ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ On the geometric priority set cover problem ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Improved Algorithm for Resource Allocation Problems ⋮ Demand Hitting and Covering of Intervals ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Approximating Sparse Covering Integer Programs Online ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ On Capacitated Set Cover Problems ⋮ Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities ⋮ Set cover problems with small neighborhood covers ⋮ On interval and circular-arc covering problems ⋮ Unnamed Item ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time

This page was built for publication: On Column-Restricted and Priority Covering Integer Programs