Exact algorithms and APX-hardness results for geometric packing and covering problems
From MaRDI portal
Publication:390102
DOI10.1016/j.comgeo.2012.04.001zbMath1283.52032OpenAlexW2124937241MaRDI QIDQ390102
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
Related Items (36)
\(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ Theoretical complexity of grid cover problems used in radar applications ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions ⋮ Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On the geometric priority set cover problem ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Geometric dominating-set and set-cover via local-search ⋮ Computational complexity for the problem of optimal intersection of straight line segments by disks ⋮ Geometric hitting set for line-constrained disks ⋮ On the approximability of covering points by lines and related problems ⋮ Unnamed Item ⋮ Improved approximation bounds for the minimum constraint removal problem ⋮ Constructing planar support for non-piercing regions ⋮ On the geometric red-blue set cover problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Unnamed Item ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ Minimum membership covering and hitting ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Maximum independent and disjoint coverage ⋮ Unnamed Item ⋮ Approximability of covering cells with line segments ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ On interval and circular-arc covering problems ⋮ A tight analysis of geometric local search
Cites Work
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- Complexities of efficient solutions of rectilinear polygon cover problems
- Improved approximation algorithms for geometric set cover
- Hitting sets when the VC-dimension is small
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Almost optimal set covers in finite VC-dimension
- Weighted geometric set cover via quasi-uniform sampling
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- On Column-Restricted and Priority Covering Integer Programs
- PTAS for Weighted Set Cover on Unit Squares
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Fast approximation algorithms for a nonconvex covering problem
- Approximation algorithms for maximum independent set of pseudo-disks
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Tight lower bounds for the size of epsilon-nets
- Lenses in arrangements of pseudo-circles and their applications
This page was built for publication: Exact algorithms and APX-hardness results for geometric packing and covering problems
