PTAS for Weighted Set Cover on Unit Squares
From MaRDI portal
Publication:3588405
DOI10.1007/978-3-642-15369-3_13zbMath1304.68214OpenAlexW1523637354MaRDI QIDQ3588405
Erlebach, Thomas, Erik Jan van Leeuwen
Publication date: 10 September 2010
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_13
Related Items (21)
\(\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 ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ On the geometric set multicover problem ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Minimum ply covering of points with unit squares ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Geometric dominating-set and set-cover via local-search ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ On the geometric red-blue set cover problem ⋮ Discrete unit square cover problem ⋮ The within-strip discrete unit disk cover problem ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ On Geometric Set Cover for Orthants ⋮ On the stab number of rectangle intersection graphs ⋮ On interval and circular-arc covering problems ⋮ On Partial Covering For Geometric Set Systems ⋮ Geometric red-blue set cover for unit squares and related problems ⋮ On Covering Segments with Unit Intervals
This page was built for publication: PTAS for Weighted Set Cover on Unit Squares
