2026-07-20T06:22:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9111 2024-03-06T10:43:23Z ddc:004 open_access

Brief Announcement: Approximation Schemes for Geometric Coverage Problems Chaplick, Steven De, Minati Ravsky, Alexander Spoerhase, Joachim balanced separators maximum coverage local search approximation scheme geometric approximation algorithms In this announcement, we show that the classical Maximum Coverage problem (MC) admits a PTAS via local search in essentially all cases where the corresponding instances of Set Cover (SC) admit a PTAS via the local search approach by Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010]. As a corollary, we answer an open question by Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding half-spaces in R^3 thereby settling the existence of PTASs for essentially all natural cases of geometric MC problems. As an intermediate result, we show a color-balanced version of the classical planar subdivision theorem by Frederickson [Greg N. Frederickson, 1987]. We believe that some of our ideas may be useful for analyzing local search in other settings involving a hard cardinality constraint. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steven Chaplick and Minati De and Alexander Ravsky and Joachim Spoerhase 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.107 urn:nbn:de:0030-drops-91113 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.107 eng https://creativecommons.org/licenses/by/3.0/legalcode