Coresets for Clustering in Excluded-minor Graphs and Beyond Article Swipe

MAKE IMPACT

Vladimir Braverman , Shaofeng H.-C. Jiang , Robert Krauthgamer , Xuan Wu · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2004.07718

Coresets are modern data-reduction tools that are widely used in data analysis to improve efficiency in terms of running time, space and communication complexity. Our main result is a fast algorithm to construct a small coreset for k-Median in (the shortest-path metric of) an excluded-minor graph. Specifically, we give the first coreset of size that depends only on $k$, $ε$ and the excluded-minor size, and our running time is quasi-linear (in the size of the input graph). The main innovation in our new algorithm is that is iterative; it first reduces 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 step in this iterative size reduction is based on the importance sampling framework of Feldman and Langberg (STOC 2011), with a crucial adaptation that reduces the number of \emph{distinct points}, by employing a terminal embedding (where low distortion is guaranteed only for the distance from every terminal to all other points). Our terminal embedding is technically involved and relies on shortest-path separators, a standard tool in planar and excluded-minor graphs. Furthermore, our new algorithm is applicable also in Euclidean metrics, by simply using a recent terminal embedding result of Narayanan and Nelson, (STOC 2019), which extends the Johnson-Lindenstrauss Lemma. We thus obtain an efficient coreset construction in high-dimensional Euclidean spaces, thereby matching and simplifying state-of-the-art results (Sohler and Woodruff, FOCS 2018; Huang and Vishnoi, STOC 2020). In addition, we also employ terminal embedding with additive distortion to obtain small coresets in graphs with bounded highway dimension, and use applications of our coresets to obtain improved approximation schemes, e.g., an improved PTAS for planar k-Median via a new centroid set.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2004.07718

PDF

https://arxiv.org/pdf/2004.07718

OA Status

green

Cited By

3

References

55

Related Works

10

OpenAlex ID

https://openalex.org/W3017295214

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3017295214

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2004.07718

Digital Object Identifier

Title

Coresets for Clustering in Excluded-minor Graphs and Beyond

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-04-16

Full publication date if available

Authors

Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu

List of authors in order

Landing page

https://arxiv.org/abs/2004.07718

Publisher landing page

PDF URL

https://arxiv.org/pdf/2004.07718

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2004.07718

Direct OA link when available

Concepts

Combinatorics, Mathematics, Embedding, Metric space, Minor (academic), Binary logarithm, Discrete mathematics, Euclidean geometry, Matching (statistics), Graph, Shortest path problem, Time complexity, Algorithm, Computer science, Statistics, Law, Political science, Geometry, Artificial intelligence

Top concepts (fields/topics) attached by OpenAlex

Cited by

3

Total citation count in OpenAlex

Citations by year (recent)

2024: 1, 2021: 1, 2020: 1

Per-year citation counts (last 5 years)

References (count)

55

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload