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

We consider the $k$-Median problem on planar graphs: given an edge-weightedplanar graph $G$, a set of clients $C \subseteq V(G)$, a set of facilities $F\subseteq V(G)$, and an integer parameter $k$, the task is to find a set of atmost $k$ facilities whose opening minimizes the total connection cost ofclients, where each client contributes to the cost with the distance to theclosest open facility. We give two new approximation schemes for this problem:-- FPT Approximation Scheme: for any $\epsilon>0$, in time$2^{O(k\epsilon^{-3}\log (k\epsilon^{-1}))}\cdot n^{O(1)}$ we can compute asolution that  (1) has connection cost at most $(1+\epsilon)$ times the optimum, with highprobability. -- Efficient Bicriteria Approximation Scheme: for any$\epsilon>0$, in time $2^{O(\epsilon^{-5}\log (\epsilon^{-1}))}\cdot n^{O(1)}$we can compute a set of at most $(1+\epsilon)k$ facilities  (2) whose opening yields connection cost at most $(1+\epsilon)$ times theoptimum connection cost for opening at most $k$ facilities, with highprobability.  As a direct corollary of the second result we obtain an EPTAS for the UniformFacility Location on planar graphs, with same running time.  Our main technical tool is a new construction of a "coreset for facilities"for $k$-Median in planar graphs: we show that in polynomial time one cancompute a subset of facilities $F_0\subseteq F$ of size $k\cdot (\logn/\epsilon)^{O(\epsilon^{-3})}$ with a guarantee that there is a$(1+\epsilon)$-approximate solution contained in $F_0$.

Efficient approximation schemes for uniform-cost clustering problems in planar graphs