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

Coresets are modern data-reduction tools that are widely used in dataanalysis to improve efficiency in terms of running time, space andcommunication complexity. Our main result is a fast algorithm to construct asmall coreset for k-Median in (the shortest-path metric of) an excluded-minorgraph. Specifically, we give the first coreset of size that depends only on$k$, $\epsilon$ and the excluded-minor size, and our running time isquasi-linear (in the size of the input graph).  The main innovation in our new algorithm is that is iterative; it firstreduces the $n$ input points to roughly $O(\log n)$ reweighted points, then to$O(\log\log n)$, and so forth until the size is independent of $n$. Each stepin this iterative size reduction is based on the importance sampling frameworkof Feldman and Langberg (STOC 2011), with a crucial adaptation that reduces thenumber of \emph{distinct points}, by employing a terminal embedding (where lowdistortion is guaranteed only for the distance from every terminal to all otherpoints). Our terminal embedding is technically involved and relies onshortest-path separators, a standard tool in planar and excluded-minor graphs.  Furthermore, our new algorithm is applicable also in Euclidean metrics, bysimply using a recent terminal embedding result of Narayanan and Nelson, (STOC2019), which extends the Johnson-Lindenstrauss Lemma. We thus obtain anefficient coreset construction in high-dimensional Euclidean spaces, therebymatching and simplifying state-of-the-art results (Sohler and Woodruff, FOCS2018; Huang and Vishnoi, STOC 2020).  In addition, we also employ terminal embedding with additive distortion toobtain small coresets in graphs with bounded highway dimension, and useapplications of our coresets to obtain improved approximation schemes, e.g., animproved PTAS for planar k-Median via a new centroid set.

Coresets for Clustering in Excluded-minor Graphs and Beyond