Exact algorithms and APX-hardness results for geometric packing and covering problems
From MaRDI portal
(Redirected from 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 -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
(58)- 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
- On line-separable weighted unit-disk coverage and related problems
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Approximation algorithms for polynomial-expansion and low-density graphs
- A tight analysis of geometric local search
- 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
- On the geometric red-blue set cover problem
- Exact algorithms and hardness results for geometric red-blue hitting set problem
- Theoretical complexity of grid cover problems used in radar applications
- Improved approximation bounds for the minimum constraint removal problem
- On the complexity of some geometric problems in unbounded dimension
- Grid intersection graphs and order dimension
- Covering, hitting, piercing and packing rectangles intersecting an inclined line
- On the geometric priority set cover problem
- Weighted geometric set cover with rectangles of bounded integer side lengths
- PTAS for minimum cost multicovering with disks
- On the line-separable unit-disk coverage and related problems
- On the geometric red-blue set cover problem
- New geometric representations and domination problems on tolerance and multitolerance graphs
- Approximation and online algorithms for multidimensional bin packing: a survey
- On line-separable weighted unit-disk coverage and related problems
- A PTAS for the horizontal rectangle stabbing problem
- Geometric packing under non-uniform constraints
- Hardness results and approximation schemes for discrete packing and domination problems
- Sweeping arrangements of non-piercing regions in the plane
- Unweighted geometric hitting set for line-constrained disks and related problems
- Local search strikes again: PTAS for variants of geometric covering and packing
- Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
- Optimality of geometric local search
- A PTAS for the horizontal rectangle stabbing problem
- Constructing planar support for non-piercing regions
- A PTAS for the Weighted Unit Disk Cover Problem
- scientific article; zbMATH DE number 7561415 (Why is no real title available?)
- 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
- On the approximability of covering points by lines and related problems
- Minimum-membership geometric dominating set: complexity and algorithms
- On Geometric Set Cover for Orthants
- Geometric dominating-set and set-cover via local-search
- Set cover, hitting set, and independent set problems for some restricted classes of geometric objects
- Polynomial-time approximation schemes for packing and piercing fat objects
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Sweeping arrangements of non-piercing regions in the plane
- Algorithms for halfplane coverage and related problems
- On approximation schemes for stabbing rectilinear polygons
- Parameterized and approximation algorithms for coverings points with segments in the plane
- On interval and circular-arc covering problems
- On the line-separable unit-disk coverage and related problems
- Dynamic geometric set cover, revisited
- 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 approximation bounds for the minimum constraint removal problem
- Improved algorithms for minimum-membership geometric set cover
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)
