Abstract
We study a geometric version of the Red-Blue Set Cover problem originally proposed by Carr, Doddi, Konjevod, and Marathe (SODA 2000): given a red point set, a blue point set, and a set of objects, we want to use objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first PTAS for this case. The technique we use simplifies and unifies previous PTASes for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares.
| Original language | English (US) |
|---|---|
| Pages | 289-293 |
| Number of pages | 5 |
| State | Published - 2013 |
| Externally published | Yes |
| Event | 25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada Duration: Aug 8 2013 → Aug 10 2013 |
Other
| Other | 25th Canadian Conference on Computational Geometry, CCCG 2013 |
|---|---|
| Country/Territory | Canada |
| City | Waterloo |
| Period | 8/8/13 → 8/10/13 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics