Pith. sign in

REVIEW 3 major objections 5 minor 52 references

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case

T0 review · 3 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that any ε-coreset construction for ordinary (k,z)-Clustering can be turned into an ε-coreset for (k,z,m)-Clustering with outliers, with size near-linear in k and only polylogarithmic overhead.

desk verdict A strong black-box reduction framework for robust clustering coresets; offline part looks solid, but the streaming theorem rests on an unproven sampling lemma. read the letter →

arxiv 2502.07669 v1 pith:RQ2YKHZF submitted 2025-02-11 cs.DS

Shaofeng H.-C. Jiang , Jianing Lou This is my paper · ORCID
classification cs.DS MSC 68W2568W27
keywords coresetsclusteringwithoutliersrobustk-mediank-meansblack-boxreductiondynamicstreamingsize-preserving
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that coresets for clustering with outliers can be built from any coreset construction for ordinary clustering, with only a small extra cost. Concretely, it claims that an $\epsilon$-coreset for $(k,z,m)$-Clustering can be produced from an $\epsilon$-coreset for $(k,z)$-Clustering of size $N$, with size $N\cdot \mathrm{poly}\log(km\epsilon^{-1}) + O_z(\min\{km\epsilon^{-1}, m\epsilon^{-2z}\log^z(km\epsilon^{-1})\})$, where $O_z$ hides a $2^{O(z\log z)}$ factor. If true, this gives the first robust clustering coresets whose size is near-linear in $k$, replacing previous bounds that grew at least quadratically in $k$, and it makes the 'price of robustness' a small additive term rather than a structural obstacle. A reader should care because coresets are the standard route to fast, streaming, and distributed clustering algorithms, and the robust-with-outliers variant has lagged behind the vanilla case.

What carries the argument

The load-bearing mechanism is a pair of sufficient conditions plus black-box reductions that enforce them. Condition I says a vanilla coreset of a dense dataset—one that admits a $\lambda$-bounded partition in which every part has at least $\Omega(\epsilon^{-1}m)$ points—is already an $O(\epsilon)$-coreset for the robust objective, because each point's contribution is charged against many nearby points. Condition II says a vanilla coreset that is size-preserving with respect to a $\lambda$-bounded partition—each part keeps exactly its original number of weighted points, so the coreset can be read as moving every point by at most $\lambda$—is robust. To make Condition I hold, an almost-dense decomposition (Lemma 3.4) splits any dataset into a dense part and a sparse remainder of only $O_z(km\epsilon^{-1})$ points. To make Condition II hold, Algorithm 2 maps the dataset into a $w$-separated duplication of the metric (each point is copied into one of $h$ layers placed far apart), computes a vanilla coreset there, and pulls it back; a sparse partition with $O(\log n)$ overlap controls the number of centers that this construction requires.

What would settle it

Find a metric from the paper's list where every $\epsilon$-coreset for $(k,z,m)$-Clustering provably needs $\Omega(k^2)$ points while vanilla coresets of size $O(k\,\mathrm{poly}(\epsilon^{-1}))$ exist; Theorem 1.1 predicts near-linear dependence on $k$ in all listed metrics, so such a lower bound would refute the central claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: any $\epsilon$-coreset construction for vanilla $(k,z)$-Clustering with size $N$ can be converted, in a black-box way, into an $\epsilon$-coreset for $(k,z,m)$-Clustering of size $\min\{N(d,k,O(\epsilon^{-1})) + O_z(km\epsilon^{-1}), N(O(d), O(k\log^2(km\epsilon^{-1})), O(\epsilon^{-1})) + O_z(m\epsilon^{-2z}\log^z(km\epsilon^{-1}))\}$. The conversion never inspects the vanilla coreset algorithm's internals. It rests on two sufficient conditions under which a vanilla coreset is automatically robust: (i) the dataset is 'dense', meaning it admits a partition into bounded-diameter parts each containing at least $\Omega(\epsilon^{-1}m)$ points, so deleting $m$ outliers changes the objective by only $O(\epsilon)$; and (ii) the vanilla coreset is 'size-preserving', meaning it keeps the same number of weighted points in each part of a bounded-diameter partition, so it can be viewed as moving every data point by only a small distance. The paper shows how to force either condition by a black-box reduction: an almost-dense decomposition that leaves only $O_z(km\epsilon^{-1})$ 'sparse' points outside the dense core, and a separated-duplication trick combined with a sparse partition that makes any vanilla coreset size-preserving at the cost of a polylogarithmic factor and a duplication of the metric whose complexity grows only by a constant in standard metric families.

Load-bearing premise

Both reductions assume as input a constant-factor approximation to the robust clustering instance with a constant-factor violation on the number of outliers, and the second reduction also assumes the metric admits separated duplications whose coreset complexity is comparable to the original metric; if either assumption fails, the stated size bounds do not follow.

Editorial extensions

If this is right

  • Plugging in known vanilla coresets gives the first coresets for $(k,z,m)$-Clustering with size near-linear in $k$ in Euclidean spaces, doubling metrics, general finite metrics, and bounded-treewidth or excluded-minor graph metrics.
  • Because the reduction is black-box, any future improvement to vanilla coreset size or construction time transfers automatically to the robust setting.
  • In the dynamic streaming model, the reductions yield the first streaming coreset algorithms for $k$-Median and $k$-Means with $m$ outliers, using space $\tilde{O}(k+m)\,\mathrm{poly}(d\epsilon^{-1}\log\Delta)$ on grid inputs.
  • The additive term becomes $O_z(k\epsilon^{-1})$ when $m=O(1)$, giving a smooth asymptotic transition from the vanilla case $m=0$ to a single outlier.
  • If the supplied vanilla coreset construction is deterministic, the entire robust coreset construction is deterministic as well.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • We infer that the same two-condition recipe—density or size-preservation—can be exported to other constrained clustering variants such as capacity, fairness, or fault-tolerant clustering, because the reduction never uses the vanilla algorithm's internals and only needs a bounded-diameter decomposition plus a size-preserving coreset.
  • We infer that the streaming implementation, which uses data-oblivious consistent hashing rather than quadtrees, opens a route to dynamic streaming coresets for other clustering variants in high dimension whenever a sparse-recovery primitive is available.
  • We infer that the next natural target is a matching lower bound for the additive term itself: the paper's bound separates the price of robustness from the vanilla size, and the $\Omega(m)$ lower bound for robust coresets already shows the linear dependence on $m$ is necessary.
  • We infer that any metric family whose complexity parameter is stable under separated duplication—as the paper shows for doubling dimension, treewidth, and excluded-minor graphs—would inherit the near-linear-in-$k$ bound without a new argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper gives black-box reductions that convert any epsilon-coreset construction for vanilla (k,z)-Clustering into an epsilon-coreset for (k,z,m)-Clustering with outliers. The first reduction (Theorem 3.1) uses a dense/sparse decomposition and adds O_z(km/epsilon) points to the vanilla coreset; the second (Theorem 4.2) uses separated duplications and sparse partitions to obtain an alternative additive bound O_z(m epsilon^{-2z} log^z(km/epsilon)). Plugging in known vanilla coresets yields the first robust coresets with size near-linear in k, and a dynamic streaming implementation (Theorem 5.1) is claimed to give the first dynamic streaming coreset algorithms for k-Median and k-Means with m outliers using space ~O(k+m) poly(d epsilon^{-1} log Delta). The streaming part depends critically on Lemma 5.4, whose proof (Appendix C.1) is only a sketch.

Significance. If the results are correct, Theorem 1.1 is a substantial advance: it gives a clean, black-box understanding of the price of robustness for coresets, obtains the first robust coresets near-linear in k in several metric families, preserves determinism when the base algorithm is deterministic, and provides the first dynamic streaming coresets for robust k-clustering. The explicit lemma structure and error bookkeeping are strengths, as is the composability treatment. The main caveats are that the streaming claims rest on an unproved bucket-elimination step (Lemma C.1) and that Theorem 4.2 uses Lemma 4.6 in a stronger form than the lemma states; these are local but load-bearing and currently block acceptance.

major comments (3)
  1. [Appendix C.1, Lemma C.1] The proof of Lemma C.1, which underpins Lemma 5.4 and hence Theorem 5.1, is only a sketch and the bucket-elimination step does not follow from the stated argument. Coloring points red/blue and observing that each two-level sample is blue with probability at least 1/2 controls the number of samples that hit B, but a blue bucket is eliminated only when all of its points have been sampled; a bucket with r points requires r successful hits to that same bucket, and sampling without replacement decreases the per-bucket success probabilities over time. The conclusion 'since |B|<=T, |phi(B\G)|<=beta' therefore needs a genuine coupon-collector-style analysis over buckets with arbitrary sizes, not just O(T log(T/delta)) samples. Because both the W1 and W2 streaming space bounds and the claimed first dynamic streaming algorithms rest on this lemma, a complete proof or a replacement argument is required.
  2. [Section 4, Lemma 4.6 vs. Theorem 4.2] Lemma 4.6 as stated proves only that the output S of Algorithm 2 is an epsilon-coreset for (k,z)-Clustering. Theorem 4.2, however, invokes the lemma to conclude that S is an epsilon-coreset for (k + beta k Lambda, z)-Clustering, and then for (k+|Q|,z)-Clustering, in order to apply Lemma 4.3. A coreset for k centers does not imply a coreset for a larger number of centers by padding, since the bridge-center bound in the proof of Lemma 4.6 grows with the number of centers. The gap is likely fixable by generalizing Lemma 4.6 to arbitrary k0 with the condition k' >= (k0+t)Lambda, which is exactly what the choice k'=(k+beta k Lambda+beta k)Lambda provides, but this generalization is not stated or proved. As written, the application in Theorem 4.2 and in Section 5.2 is unsupported.
  3. [Section 3.1, Lemma 3.3] In the proof of Lemma 3.3, inequality (7) is dismissed as 'similar' to inequality (6), but the tool used for (6), Lemma 3.5, applies only to a dataset whose parts are dense. The coreset S is a weighted set and is not shown to satisfy the dense-partition condition |P| >= (1+epsilon^{-1})m on any partition. Some additional argument is needed, for example showing from the vanilla coreset guarantee that w_S(S cap P) is close to |P| for every dense part P, or proving a weighted analogue of Lemma 3.5. This is load-bearing for Theorem 3.1, since (7) is used to bound the difference between robust and vanilla costs on S.
minor comments (5)
  1. [Definition 4.1] The heading 'Seperated duplication of a metric space' contains a typo; it should be 'Separated duplication'.
  2. [Algorithm 4, line 4] The notation 'XS <- sum_{P in S} P' is informal; it should be written as 'XS <- union_{P in S} P' or with explicit set-builder notation.
  3. [Lemma 5.5] The lemma title 'Indentify Sparse Subsets' contains a typo; it should be 'Identify Sparse Subsets'.
  4. [Section 5.1] The subsection heading 'Removing Assumption of Knowing dOPT' appears to have a typo: 'dOPT' should be '[OPT' or 'OPT'.
  5. [Lemma 5.4] The statement says the algorithm samples 'a random subset G' but the proof describes sampling without replacement via l0-samplers; the precise sense in which G is random should be clarified, since it is not uniform over subsets of X.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the offline reductions prove robust coresets from vanilla coresets plus approximation and decomposition, never assuming the target robust bound.

full rationale

The central derivation is self-contained conditional on the stated black-box input. Theorem 3.1 takes a tri-criteria approximation C* (Definition 2.4) and a vanilla coreset algorithm, proves via Lemma 3.4 and Lemma 3.3 that a robust coreset follows; the target robust guarantee is not assumed anywhere in the proof. Theorem 4.2 similarly proves that a size-preserving vanilla coreset is robust (Lemma 4.3) and provides a black-box conversion (Algorithm 2 / Lemma 4.6) whose bridge-center argument is built from the vanilla coreset guarantee on a separated duplication, not from the robust conclusion. The heavy tools cited from coauthored prior work — consistent hashing [CFJ+22, Lemma 5.2] and the two-level l0-sampler [CFJ+22, Lemma 3.3] — are external geometric/streaming lemmas with stated assumptions that do not include the robust coreset result, so they are genuine independent evidence rather than circularity. The Omega(m) lower-bound comparison to [HJLW23] is contextual and does not carry the derivation. Per the reviewing rule, I flag that Appendix C.1's Lemma C.1 is presented only as a proof sketch and the bucket-elimination step is not fully expanded; this is a correctness/completeness concern in the streaming claim, not an instance of the derivation reducing to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No numeric parameter is fitted to data. Constants such as lambda, w, mu, and Gamma are explicit functions of epsilon, m, OPT, and the metric parameters, and the unknown OPT is handled by a standard guessing or enumeration procedure in the streaming setting. All nonstandard algorithmic ingredients are imported as cited black boxes or proved in appendices.

assumptions (5)
  • domain assumption A (2^{O(z)}, O(1), O(1))-approximation C* to (k,z,m)-Clustering is available or computable in near-linear time.
    Used as input to Theorems 3.1 and 4.2; the almost-dense decomposition in Lemma 3.4 and the sparse-point bounds start from C*. The paper cites BVX19 and FKRS19 for this approximation.
  • domain assumption The vanilla coreset algorithm A in the premise exists for the metric and returns an epsilon-coreset of size N for all center sets.
    The entire reduction is conditional on this black box; correctness of Theorems 3.1, 4.2, and 5.1 is stated relative to A and N.
  • domain assumption Sparse partition theorem of Jia, Lin, Noubir, Rajaraman, and Sundaram: every n-point metric admits a (mu, O(log n), O(log n))-sparse partition.
    Used in Algorithm 2 and Lemma 4.6 to control how many partition parts intersect a small ball. Cited, not reproved in this paper.
  • domain assumption Consistent hashing of CFJ+22 gives a data-oblivious sparse partition of R^d with Gamma = O(d), Lambda = O(d log d), evaluable in poly(d) space.
    The streaming Section 5 uses this hashing to define lambda-bounded buckets without storing the partition. It is a cited prior result.
  • standard math Generalized triangle inequalities from MMR19 and SW18 hold for z >= 1.
    Used repeatedly in Lemma 3.5, Lemma 4.11, Lemma 4.13, and Lemma 4.14 to convert distance bounds into z-th power bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Coresets for Robust Clustering via Black-box Reductions to Vanilla Case." pith.science (2026). https://pith.science/paper/RQ2YKHZF

@misc{pith2026250207669,
  author       = {Pith},
  title        = {Pith review of: Coresets for Robust Clustering via Black-box Reductions to Vanilla Case},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQ2YKHZF}},
  note         = {Machine review of arXiv:2502.07669}
}
abstract

We devise $\epsilon$-coresets for robust $(k,z)$-Clustering with $m$ outliers through black-box reductions to vanilla case. Given an $\epsilon$-coreset construction for vanilla clustering with size $N$, we construct coresets of size $N\cdot \mathrm{poly}\log(km\epsilon^{-1}) + O_z\left(\min\{km\epsilon^{-1}, m\epsilon^{-2z}\log^z(km\epsilon^{-1}) \}\right)$ for various metric spaces, where $O_z$ hides $2^{O(z\log z)}$ factors. This increases the size of the vanilla coreset by a small multiplicative factor of $\mathrm{poly}\log(km\epsilon^{-1})$, and the additive term is up to a $(\epsilon^{-1}\log (km))^{O(z)}$ factor to the size of the optimal robust coreset. Plugging in vanilla coreset results of [Cohen-Addad et al., STOC'21], we obtain the first coresets for $(k,z)$-Clustering with $m$ outliers with size near-linear in $k$ while previous results have size at least $\Omega(k^2)$ [Huang et al., ICLR'23; Huang et al., SODA'25]. Technically, we establish two conditions under which a vanilla coreset is as well a robust coreset. The first condition requires the dataset to satisfy special structures - it can be broken into "dense" parts with bounded diameter. We combine this with a new bounded-diameter decomposition that has only $O_z(km \epsilon^{-1})$ non-dense points to obtain the $O_z(km \epsilon^{-1})$ additive bound. Another condition requires the vanilla coreset to possess an extra size-preserving property. We further give a black-box reduction that turns a vanilla coreset to the one satisfying the said size-preserving property, leading to the alternative $O_z(m\epsilon^{-2z}\log^{z}(km\epsilon^{-1}))$ additive bound. We also implement our reductions in the dynamic streaming setting and obtain the first streaming algorithms for $k$-Median and $k$-Means with $m$ outliers, using space $\tilde{O}(k+m)\cdot\mathrm{poly}(d\epsilon^{-1}\log\Delta)$ for inputs on the grid $[\Delta]^d$.

Figures

Figures reproduced from arXiv: 2502.07669 by the authors.

Figure 1
Figure 1. Illustration of the construction of separated duplication of a graph with the weights of [PITH_FULL_IMAGE:figures/full_fig_p044_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 48 canonical work pages

  1. [1]

    Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H

    Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In ICML , volume 119 of Proceedings of Machine Learning Research , pages 569--579. PMLR , 2020

    work page 2020

  2. [2]

    Vladimir Braverman, Vincent Cohen - Addad, Shaofeng H. - C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In FOCS , pages 462--473. IEEE , 2022

    work page 2022

  3. [3]

    Distributed k-means and k-median clustering on general communication topologies

    Maria - Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. In NIPS , pages 1995--2003, 2013

    work page 1995

  4. [4]

    Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang. Clustering high dimensional dynamic data streams. In ICML , volume 70 of Proceedings of Machine Learning Research , pages 576--585. PMLR , 2017

    work page 2017

  5. [5]

    Fomin, and Kirill Simonov

    Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. In ICALP , volume 198 of LIPIcs , pages 23:1--23:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

    work page 2021

  6. [6]

    Vladimir Braverman, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In ICML , volume 97 of Proceedings of Machine Learning Research , pages 744--753. PMLR , 2019

    work page 2019

  7. [7]

    Vladimir Braverman, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In SODA , pages 2679--2696. SIAM , 2021

    work page 2021

  8. [8]

    Vladimir Braverman, Shaofeng H. - C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering with missing values. In NeurIPS , pages 17360--17372, 2021

    work page 2021

Show all 52 references
  1. [9]

    Greedy sampling for approximate clustering in the presence of outliers

    Aditya Bhaskara, Sharvaree Vadgama, and Hong Xu. Greedy sampling for approximate clustering in the presence of outliers. In NeurIPS , pages 11146--11155, 2019

    2019

  2. [10]

    A tight vc-dimension analysis of clustering coresets with applications

    Vincent Cohen - Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight vc-dimension analysis of clustering coresets with applications. In SODA , pages 4783--4808. SIAM , 2025

    2025

  3. [11]

    Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang

    Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. arXiv preprint arXiv:2204.02095 , 2022. The latest version has additional results compared to the prelim...

    2022 arXiv

  4. [12]

    On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications

    Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput. , 39(3):923--947, 2009

    2009

  5. [13]

    Artur Czumaj, Shaofeng H. - C. Jiang, Robert Krauthgamer, Pavel Vesel \' y , and Mingwei Yang. Streaming facility location in high dimension via geometric hashing. In FOCS , pages 450--461. IEEE , 2022

    2022

  6. [14]

    Fair clustering through fairlets

    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In NIPS , pages 5029--5037, 2017

    2017

  7. [15]

    Mount, and Giri Narasimhan

    Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In SODA , pages 642--651. ACM/SIAM , 2001

    2001

  8. [16]

    On the fixed-parameter tractability of capacitated clustering

    Vincent Cohen - Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In ICALP , volume 132 of LIPIcs , pages 41:1--41:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019

    2019

  9. [17]

    Improved coresets for euclidean k-means

    Vincent Cohen - Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh - Omar. Improved coresets for euclidean k-means. In NeurIPS , 2022

    2022

  10. [18]

    Towards optimal lower bounds for k-median and k-means coresets

    Vincent Cohen - Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC , pages 1038--1051. ACM , 2022

    2022

  11. [19]

    Muthukrishnan

    Graham Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. In CISS , pages 198--201. IEEE , 2006

    2006

  12. [20]

    A new coreset framework for clustering

    Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC , pages 169--182. ACM , 2021

    2021

  13. [21]

    Deterministic clustering in high dimensional spaces: Sketches and approximation

    Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. Deterministic clustering in high dimensional spaces: Sketches and approximation. In FOCS , pages 1105--1130. IEEE , 2023

    2023

  14. [22]

    Core-sets: An updated survey

    Dan Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl. Discov. , 10(1), 2020

    2020

  15. [23]

    Scattering and sparse partitions, and their applications

    Arnold Filtser. Scattering and sparse partitions, and their applications. In ICALP , volume 168 of LIPIcs , pages 47:1--47:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  16. [24]

    Salavatipour

    Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximation schemes for clustering with outliers. ACM Trans. Algorithms , 15(2):26:1--26:26, 2019

    2019

  17. [25]

    A unified framework for approximating and clustering data

    Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In STOC , pages 569--578. ACM , 2011. https://arxiv.org/abs/1106.1379

    2011 arXiv

  18. [26]

    Data reduction for weighted and outlier-resistant clustering

    Dan Feldman and Leonard J Schulman. Data reduction for weighted and outlier-resistant clustering. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 1343--1354. SIAM, 2012

    2012

  19. [27]

    Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering

    Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering. SIAM J. Comput. , 49(3):601--657, 2020

    2020

  20. [28]

    Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS , pages 534--543. IEEE Computer Society, 2003

    2003

  21. [29]

    On coresets for clustering in small dimensional euclidean spaces

    Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang, and Xuan Wu. On coresets for clustering in small dimensional euclidean spaces. In ICML , volume 202 of Proceedings of Machine Learning Research , pages 13891--13915. PMLR , 2023

    2023

  22. [30]

    Lingxiao Huang, Shaofeng H. - C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In FOCS , pages 814--825. IEEE Computer Society, 2018

    2018

  23. [31]

    Lingxiao Huang, Shaofeng H. - C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In ICLR . OpenReview.net, 2023

    2023

  24. [32]

    Lingxiao Huang, Shaofeng H. - C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with fairness constraints. In NeurIPS , pages 7587--7598, 2019

    2019

  25. [33]

    Smaller coresets for k -median and k -means clustering

    Sariel Har - Peled and Akash Kushal. Smaller coresets for k -median and k -means clustering. Discret. Comput. Geom. , 37(1):3--19, 2007

    2007

  26. [34]

    Fully-dynamic coresets

    Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In ESA , volume 173 of LIPIcs , pages 57:1--57:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    2020

  27. [35]

    Coresets for constrained clustering: General assignment constraints and improved size bounds

    Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. In SODA , pages 4732--4782. SIAM , 2025

    2025

  28. [36]

    On optimal coreset construction for euclidean (k, z) -clustering

    Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for euclidean (k, z) -clustering. In STOC , pages 1594--1604. ACM , 2024

    2024

  29. [37]

    On coresets for k -means and k -median clustering

    Sariel Har - Peled and Soham Mazumdar. On coresets for k -means and k -median clustering. In STOC , pages 291--300. ACM , 2004. https://arxiv.org/abs/1810.12826

    2004 arXiv

  30. [38]

    Yang, and Peilin Zhong

    Wei Hu, Zhao Song, Lin F. Yang, and Peilin Zhong. Nearly optimal dynamic k -means clustering for high-dimensional data. CoRR , abs/1802.00459, 2018

    2018 arXiv

  31. [39]

    Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In STOC , pages 1416--1429. ACM , 2020

    2020

  32. [40]

    Algorithms for dynamic geometric problems over data streams

    Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In STOC , pages 373--380. ACM , 2004

    2004

  33. [41]

    T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of hamming distance. Theory Comput. , 4(1):129--135, 2008

    2008

  34. [42]

    Universal approximations for tsp, steiner tree, and set cover

    Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for tsp, steiner tree, and set cover. In STOC , pages 386--395. ACM , 2005

    2005

  35. [43]

    Communication complexity

    Eyal Kushilevitz and Noam Nisan. Communication complexity . Cambridge University Press, 1997

    1997

  36. [44]

    On randomized one-round communication complexity

    Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Comput. Complex. , 8(1):21--49, 1999

    1999

  37. [45]

    Sussmann

    Samir Khuller, Robert Pless, and Yoram J. Sussmann. Fault tolerant k-center problems. Theor. Comput. Sci. , 242(1-2):237--245, 2000

    2000

  38. [46]

    Coreset for line-sets clustering

    Sagi Lotan, Ernesto Evgeniy Sanches Shayda, and Dan Feldman. Coreset for line-sets clustering. In NeurIPS , 2022

    2022

  39. [47]

    k-means clustering of lines for big data

    Yair Marom and Dan Feldman. k-means clustering of lines for big data. In NeurIPS , pages 12797--12806, 2019

    2019

  40. [48]

    Razenshteyn

    Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In STOC , pages 1027--1038. ACM , 2019

    2019

  41. [49]

    Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms

    Alexander Munteanu and Chris Schwiegelshohn. Coresets-methods and history: A theoreticians design pattern for approximation and streaming algorithms. K \" u nstliche Intell. , 32(1):37--53, 2018

    2018

  42. [50]

    Fair coresets and streaming algorithms for fair k-means

    Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In WAOA , volume 11926 of Lecture Notes in Computer Science , pages 232--251. Springer, 2019

    2019

  43. [51]

    Woodruff

    Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In FOCS , pages 802--813. IEEE Computer Society, 2018

    2018

  44. [52]

    New coresets for projective clustering and applications

    Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In AISTATS , volume 151 of Proceedings of Machine Learning Research , pages 5391--5415. PMLR , 2022

    2022

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.