Approximation Schemes for Covering and Packing
From MaRDI portal
Abstract: The local search framework for obtaining PTASs for NP-hard geometric optimization problems was introduced, independently, by Chan and Har-Peled (2009) and Mustafa and Ray (2010). In this paper, we generalize the framework by extending its analysis to additional families of graphs, beyond the family of planar graphs. We then present several applications of the generalized framework, some of which are very different from those presented to date (using the original framework). These applications include PTASs for finding a maximum l-shallow set of a set of fat objects, for finding a maximum triangle matching in an l-shallow unit disk graph, and for vertex-guarding a (not-necessarily-simple) polygon under an appropriate shallowness assumption. We also present a PTAS (using the original framework) for the important problem where one has to find a minimum-cardinality subset of a given set of disks (of varying radii) that covers a given set of points, and apply it to a class cover problem (studied in Bereg et al., 2012) to obtain an improved solution.
Recommendations
- Approximation algorithms for covering/packing integer programs
- scientific article; zbMATH DE number 1263202
- scientific article; zbMATH DE number 1839427
- Approximation schemes for multidimensional packing
- On the complexity of asymptotically optimal coverings and packings
- Packing-based approximation algorithm for the k-set cover problem
- An Approximation Algorithm for the General Mixed Packing and Covering Problem
- scientific article; zbMATH DE number 823166
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
Cited in
(28)- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Packing and covering with non-piercing regions
- A tight analysis of geometric local search
- On the geometric set multicover problem
- Existence of planar support for geometric hypergraphs using elementary techniques
- Constructing planar support for non-piercing regions
- A PTAS for the disk cover problem of geometric objects
- An algorithmic framework for solving geometric covering problems -- with applications
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- scientific article; zbMATH DE number 1241839 (Why is no real title available?)
- scientific article; zbMATH DE number 2163022 (Why is no real title available?)
- Polynomial-time approximation schemes for packing and piercing fat objects
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- On Geometric Set Cover for Orthants
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Optimality of geometric local search
- Limits of local search: quality and efficiency
- Local search strikes again: PTAS for variants of geometric covering and packing
- On the geometric priority set cover problem
- Geometric stabbing via threshold rounding and factor revealing LPs
- Generalized class cover problem with axis-parallel strips
- Online class cover problem
- Robustly guarding polygons
- Geometric covering via extraction theorem
- Covering simple orthogonal polygons with rectangles
- On supports for graphs of bounded genus
This page was built for publication: Approximation Schemes for Covering and Packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4914438)
