Approximation Schemes for Covering and Packing

DOI10.1007/978-3-642-36065-7_10zbMath1379.68344arXiv1209.5199OpenAlexW2152726660MaRDI QIDQ4914438

Yelena Yuditsky, Rom Aschner, Gila Morgenstern, Matthew J. Katz

Publication date: 12 April 2013

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (14)

On the geometric set multicover problem ⋮ Existence of planar support for geometric hypergraphs using elementary techniques ⋮ On the geometric priority set cover problem ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Unnamed Item ⋮ Constructing planar support for non-piercing regions ⋮ Packing and covering with non-piercing regions ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Unnamed Item ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Approximability of covering cells with line segments ⋮ A tight analysis of geometric local search

This page was built for publication: Approximation Schemes for Covering and Packing