English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Weighted geometric set-cover problems arise naturally in several geometricand non-geometric settings (e.g. the breakthrough of Bansal-Pruhs (FOCS 2010)reduces a wide class of machine scheduling problems to weighted geometricset-cover). More than two decades of research has succeeded in settling the$(1+\epsilon)$-approximability status for most geometric set-cover problems,except for four basic scenarios which are still lacking. One is that ofweighted disks in the plane for which, after a series of papers, Varadarajan(STOC 2010) presented a clever \emph{quasi-sampling} technique, which togetherwith improvements by Chan \etal~(SODA 2012), yielded a $O(1)$-approximationalgorithm. Even for the unweighted case, a PTAS for a fundamental class ofobjects called pseudodisks (which includes disks, unit-height rectangles,translates of convex sets etc.) is currently unknown. Another fundamental caseis weighted halfspaces in $\Re^3$, for which a PTAS is currently lacking. Inthis paper, we present a QPTAS for all of these remaining problems. Our resultsare based on the separator framework of Adamaszek-Wiese (FOCS 2013, SODA 2014),who recently obtained a QPTAS for weighted independent set of polygonalregions. This rules out the possibility that these problems are APX-hard,assuming $\textbf{NP} \nsubseteq \textbf{DTIME}(2^{polylog(n)})$. Together withthe recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness statusfor all natural geometric set-cover problems.

QPTAS for Geometric Set-Cover Problems via Optimal Separators