Exact algorithms and APX-hardness results for geometric packing and covering problems
From MaRDI portal
Publication:390102
DOI10.1016/J.COMGEO.2012.04.001zbMATH Open1283.52032OpenAlexW2124937241MaRDI QIDQ390102FDOQ390102
Publication date: 22 January 2014
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.04.001
Recommendations
- Improved approximation algorithms for geometric set cover
- Improved approximation algorithms for geometric set cover
- Local search strikes again: PTAS for variants of geometric covering and packing
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
Cites Work
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Hitting sets when the VC-dimension is small
- Almost optimal set covers in finite VC-dimension
- Weighted geometric set cover via quasi-uniform sampling
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Fast approximation algorithms for a nonconvex covering problem
- Title not available (Why is that?)
- Improved results on geometric hitting set problems
- Title not available (Why is that?)
- On Column-Restricted and Priority Covering Integer Programs
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Approximation algorithms for maximum independent set of pseudo-disks
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- PTAS for Weighted Set Cover on Unit Squares
- Tight lower bounds for the size of epsilon-nets
- Lenses in arrangements of pseudo-circles and their applications
- Complexities of efficient solutions of rectilinear polygon cover problems
- Improved approximation algorithms for geometric set cover
Cited In (43)
- Algorithms for the line-constrained disk coverage and related problems
- Algorithms for the line-constrained disk coverage and related problems
- Geometric hitting set for line-constrained disks
- Recognition and drawing of stick graphs
- A tight analysis of geometric local search
- Title not available (Why is that?)
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- On the geometric red-blue set cover problem
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- Theoretical complexity of grid cover problems used in radar applications
- On the complexity of some geometric problems in unbounded dimension
- On the geometric priority set cover problem
- PTAS for minimum cost multicovering with disks
- Grid intersection graphs and order dimension
- Weighted geometric set cover with rectangles of bounded integer side lengths
- On the line-separable unit-disk coverage and related problems
- New geometric representations and domination problems on tolerance and multitolerance graphs
- Approximation and online algorithms for multidimensional bin packing: a survey
- A PTAS for the horizontal rectangle stabbing problem
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Approximability of covering cells with line segments
- Minimum membership covering and hitting
- Local search strikes again: PTAS for variants of geometric covering and packing
- A PTAS for the horizontal rectangle stabbing problem
- Title not available (Why is that?)
- A PTAS for the Weighted Unit Disk Cover Problem
- Constructing planar support for non-piercing regions
- On the approximability of covering points by lines and related problems
- Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
- On Geometric Set Cover for Orthants
- Geometric dominating-set and set-cover via local-search
- Polynomial-time approximation schemes for packing and piercing fat objects
- Title not available (Why is that?)
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Title not available (Why is that?)
- On interval and circular-arc covering problems
- Maximum independent and disjoint coverage
- Computational complexity for the problem of optimal intersection of straight line segments by disks
- An exact algorithm for a class of geometric set-cover problems
- Improved algorithms for minimum-membership geometric set cover
- Improved approximation bounds for the minimum constraint removal problem
This page was built for publication: Exact algorithms and APX-hardness results for geometric packing and covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390102)
