Exact algorithms and APX-hardness results for geometric packing and covering problems
From MaRDI portal
Publication:390102
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
- scientific article; zbMATH DE number 3289061 (Why is no real title available?)
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Complexities of efficient solutions of rectilinear polygon cover problems
- Computational geometry. Algorithms and applications.
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Fast approximation algorithms for a nonconvex covering problem
- Hitting sets when the VC-dimension is small
- Improved approximation algorithms for geometric set cover
- Improved results on geometric hitting set problems
- Lenses in arrangements of pseudo-circles and their applications
- On column-restricted and priority covering integer programs
- Optimization, approximation, and complexity classes
- PTAS for weighted set cover on unit squares
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Some APX-completeness results for cubic graphs
- Tight lower bounds for the size of epsilon-nets
- Weighted geometric set cover problems revisited
- Weighted geometric set cover via quasi-uniform sampling
Cited in
(45)- Hardness results and approximation schemes for discrete packing and domination problems
- Optimality of geometric local search
- \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
- scientific article; zbMATH DE number 7561415 (Why is no real title available?)
- On the geometric red-blue set cover problem
- Polynomial-time approximation schemes for packing and piercing fat objects
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- New geometric representations and domination problems on tolerance and multitolerance graphs
- A PTAS for the horizontal rectangle stabbing problem
- Covering, hitting, piercing and packing rectangles intersecting an inclined line
- A tight analysis of geometric local search
- An exact algorithm for a class of geometric set-cover problems
- Approximation algorithms for polynomial-expansion and low-density graphs
- A PTAS for the Weighted Unit Disk Cover Problem
- Theoretical complexity of grid cover problems used in radar applications
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Improved algorithms for minimum-membership geometric set cover
- Algorithms for the line-constrained disk coverage and related problems
- Algorithms for the line-constrained disk coverage and related problems
- On the line-separable unit-disk coverage and related problems
- Constructing planar support for non-piercing regions
- Approximation and online algorithms for multidimensional bin packing: a survey
- Improved approximation bounds for the minimum constraint removal problem
- Weighted geometric set cover with rectangles of bounded integer side lengths
- Computational complexity for the problem of optimal intersection of straight line segments by disks
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- On the complexity of some geometric problems in unbounded dimension
- On Geometric Set Cover for Orthants
- Geometric dominating-set and set-cover via local-search
- PTAS for minimum cost multicovering with disks
- Grid intersection graphs and order dimension
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Geometric hitting set for line-constrained disks
- On interval and circular-arc covering problems
- Geometric packing under non-uniform constraints
- Improved approximation bounds for the minimum constraint removal problem
- Maximum independent and disjoint coverage
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Local search strikes again: PTAS for variants of geometric covering and packing
- On the approximability of covering points by lines and related problems
- On the geometric priority set cover problem
- Minimum membership covering and hitting
- Covering and packing of triangles intersecting a straight line
- Local search strikes again: PTAS for variants of geometric covering and packing
- A PTAS for the horizontal rectangle stabbing 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)
