Output details
11 - Computer Science and Informatics
University of Leicester
Output title
Approximating Geometric Coverage Problems
Type
E - Conference contribution
DOI
-
Name of conference/published proceedings
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008, San Francisco, CA)
Volume number
-
Issue number
-
First page of article
1267
ISSN of proceedings
-
Year of publication
2008
Number of additional authors
1
Additional information
<12>The paper applies technically advanced variants of the shifting strategy to geometric versions of coverage problems (considering unit disks and unit squares in the plane), showing that these admit better approximation than coverage problems in arbitrary graphs. Previously these problems had been treated in the setting of arbitrary graphs, but the motivating application is of geometric nature. By showing the better approximability for the geometric variant, the paper led to further work on geometric unique coverage problems e,g. by Ito et al. (SWAT 2012) and Chan and Hu (CCCG 2013) for unique coverage with unit squares.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
5
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
