2 października 2018 11:15
Joachim Spoerhase o "Approximation Schemes for Geometric Coverage Problems"
Tytuł: Approximation Schemes for Geometric Coverage Problems
Autorzy: Steven Chaplick, Minati De, Alexander Ravsky, Joachim Spoerhase
Prelegent: Joachim Spoerhase
Czas i miejsce: wtorek, 2-go października 2018, 11:15, sala 310
Opublikowano na ESA'18
Artykuł: https://arxiv.org/abs/
Streszczenie:
In their seminal work, Mustafa and Ray [2010] showed that a wide class
of geometric set cover (SC) problems admit a PTAS via local search -
this is one of the most general approaches known for such problems.
Their result applies if a naturally defined "exchange graph" for two
feasible solutions is planar and is based on subdividing this graph via
a planar separator theorem due to Frederickson [Greg N. Frederickson,
1987]. Obtaining similar results for the related maximum coverage
problem (MC) seems non-trivial due to the hard cardinality constraint.
In fact, while Badanidiyuru, Kleinberg, and Lee [2012] have shown (via a
different analysis) that local search yields a PTAS for two-dimensional
real halfspaces, they only conjectured that the same holds true for
dimension three. Interestingly, at this point it was already known that
local search provides a PTAS for the corresponding set cover case and
this followed directly from the approach of Mustafa and Ray. In this
work we provide a way to address the above-mentioned issue. First, we
propose a color-balanced version of the planar separator theorem. The
resulting subdivision approximates locally in each part the global
distribution of the colors. Second, we show how this roughly balanced
subdivision can be employed in a more careful analysis to strictly obey
the hard cardinality constraint. More specifically, we obtain a PTAS for
any "planarizable" instance of MC and thus essentially for all cases
where the corresponding SC instance can be tackled via the approach of
Mustafa and Ray. As a corollary, we confirm the conjecture of
Badanidiyuru, Kleinberg, and Lee regarding real halfspaces in dimension
three. We feel that our ideas could also be helpful in other geometric
settings involving a cardinality constraint.