Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

On Approximability of $\ell_2^2$ Min-Sum Clustering

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

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

Pith's one-line read Min-sum clustering is APX-hard at factor 1.056.

desk verdict First APX-hardness for ℓ2^2 min-sum clustering is real, and the stress-test's flagship objection does not survive a careful computation of the sampling correlation. read the letter →

arxiv 2412.03332 v2 pith:HPU3CUSO submitted 2024-12-04 cs.DS cs.CCcs.CGcs.LG

Karthik C. S. , Euiwoong Lee , Yuval Rabani , Chris Schwiegelshohn , Samson Zhou This is my paper · ORCID
classification cs.DScs.CCcs.CGcs.LG MSC 68Q1768W25
keywords squaredEuclideanmin-sumclusteringhardnessofapproximationAPX-hardJohnsonCoverageHypothesisdensebalancedparameterizedPTASD2samplinglearning-augmentedalgorithms
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

The paper establishes the first hardness-of-approximation barrier for $\ell_2^2$ min-sum $k$-clustering, a density-based clustering objective that can capture ring-shaped or overlapping clusters where centroid-based methods like $k$-means fail. It proves that no polynomial-time algorithm can approximate the optimal partition within a factor better than $1.056$ unless $P=NP$, and it pushes the barrier to $1.327$ under a new balanced dense Johnson Coverage hypothesis. On the positive side, it gives a nearly linear time parameterized PTAS running in $O(n^{1+o(1)}d\exp((k\varepsilon^{-1})^{O(1)}))$, and a learning-augmented algorithm that achieves a $(1+\gamma\alpha)/(1-\alpha)^2$ approximation from a label oracle with error rate $\alpha$, which beats the NP-hard barrier for sufficiently accurate oracles. These results close the gap between NP-hardness and approximability for this objective and map what polynomial-time algorithms can and cannot do.

What carries the argument

The load-bearing construction for hardness is the Johnson Coverage reduction with a balanced completeness property. In the Johnson Coverage Problem one is given a collection of $z$-element subsets over a universe and must cover them with $k$ chosen $(z-1)$-sets; the balanced dense version used here assumes $|E|=\omega(k)$ and, in completeness, a $\delta$-balanced assignment of every $z$-set to one of the covering $(z-1)$-sets. The reduction turns each $z$-set into a characteristic vector, making pairwise squared distance a function of intersection size, and the proof's crucial new mechanism is Theorem 2.6's balanced analysis of the known reduction from multilayered PCPs to 3-hypergraph vertex coverage: the produced hypergraph is almost regular, with each vertex's incident hyperedge weight equal to $(3\pm o(1))$ times its vertex weight, and in the completeness case each selected vertex can be assigned a $2/3\pm O(\delta)$ fraction of its incident hyperedges. This is what lets the soundness side decode $k$ covering sets without hidden small clusters. The PTAS uses a different mechanism, a D2-sampling tree with pruning and exhaustive mean extraction that finds $\varepsilon$-approximate means for every optimal cluster, and the learning-augmented result uses the identity $\sum_{p,q\in C}\lVert p-q\rVert_2^2=2|C|\sum_{p\in C}\lVert p-c\rVert_2^2$ together with a constrained min-cost flow that assigns points to learned centers while respecting oracle cluster sizes.

What would settle it

Take the reduction in Theorem 2.6 and compute, on explicit instances, the ratio between each vertex's weight and the total weight of hyperedges containing it, together with the maximum fraction of incident hyperedge weight assignable to a vertex in the completeness case: if any vertex's ratio deviates from $3\pm o(1)$ or no assignment gives every selected vertex $2/3\pm O(\delta)$ of its incident hyperedge weight, the $1.056$ gap collapses. For the conditional claim, refuting the balanced dense Johnson Coverage conjecture (for example, by showing that dense hardness constructions cannot be made $0$-balanced in completeness) would eliminate the $1.327$ barrier while leaving the rest of Theorem 1.3 intact.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: $\ell_2^2$ min-sum $k$-clustering is APX-hard, with an explicit constant inapproximability factor. Starting from an instance of the Johnson Coverage Problem, the reduction represents each $z$-set by its characteristic vector in $\{0,1\}^n$, so that the squared distance between two points is $\lVert p_T-p_{T'}\rVert_2^2 = 2z-2|T\cap T'|$. In the completeness case, a balanced covering family of $(z-1)$-sets partitions the points into $k$ clusters whose internal pairwise distances are all $2(z-y)$, giving cost about $2(z-y)m^2/k$; in the soundness case any $k$-clustering has many pairs at distance $2(z-y)+2$, and a convexity argument over cluster sizes gives a soundness cost of $2|P|^2(\alpha\sqrt{z-y}+(1-\alpha)\sqrt{z-y+1})^2/k$ against the completeness cost $2(z-y)|P|^2/k$. Plugging the $\alpha = 7/8+\varepsilon$ guarantee for $z=3$, obtained from a new balanced analysis of the known reduction from multilayered PCPs to 3-hypergraph vertex coverage (Theorem 2.6), gives the unconditional $1.056$ hardness; plugging the conjectured balanced dense Johnson Coverage gap $\alpha = 1-1/e+\varepsilon$ gives the conditional $1.327$ hardness.

Load-bearing premise

The unconditional $1.056$ hardness rests on the new claim that the known PCP-to-3-hypergraph reduction can be made balanced, namely that in the completeness case each selected vertex covers a $2/3\pm O(\delta)$ fraction of its incident hyperedges and the instance is almost regular; the conditional $1.327$ hardness additionally rests on the unproven balanced dense Johnson Coverage conjecture.

Editorial extensions

If this is right

  • The open question of whether $\ell_2^2$ min-sum $k$-clustering is APX-hard is resolved: unless $P=NP$, no PTAS exists and any polynomial-time approximation algorithm has an explicit constant-factor gap.
  • If the balanced dense Johnson Coverage hypothesis holds, the same reduction lifts the gap to $1.327$, extending the Johnson Coverage based hardness framework from centroid-based clustering to density-based clustering.
  • For fixed $k$ and $\varepsilon$, the parameterized PTAS runs in $n^{1+o(1)}d\exp((k\varepsilon^{-1})^{O(1)})$ time, so the problem becomes tractable at nearly linear scaling when the number of clusters and accuracy requirements are constant.
  • A label oracle with error rate $\alpha<1/2$ yields a $(1+\gamma\alpha)/(1-\alpha)^2$ approximation, and for sufficiently accurate advice this beats the $1.056$ barrier, so machine-learned labels provably convert into better worst-case guarantees.

Reading between the lines

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

  • Beyond the paper: the same characteristic-vector reduction is a template for hardness of other pairwise-cost clustering objectives whose cost is governed by intersection sizes; one could try to adapt it to $\ell_2^p$ or kernelized variants with different coverage gaps.
  • Beyond the paper: the learning-augmented min-cost flow construction does not use convexity of clusters, so it may extend to min-sum clustering with outliers or to the metric setting once a learned center oracle is available.
  • Beyond the paper: the balance property singled out in Theorem 2.6 is computationally checkable on the small hypergraphs produced by the PCP reduction; running such a check on explicit instances would be a cheap empirical sanity test of the regularity claim, even though NP-hardness itself is not empirically refutable.
Share X Bluesky LinkedIn Reddit HN

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 studies the ℓ2^2 min-sum k-clustering problem and claims three results: (i) NP-hardness of approximation to a factor better than 1.056, and 1.327 under a new Balanced-JCH* hypothesis; (ii) a parameterized PTAS running in n^{1+o(1)} d exp((k/ε)^{O(1)}) time; and (iii) a learning-augmented algorithm with approximation (1+γ α)/(1−α)^2. The hardness is obtained by reducing from Johnson Coverage instances, with the new technical core being Theorem 2.6, which asserts a balanced completeness property of the [CKL22] reduction. The PTAS combines D2 sampling with a pruning and bucketing strategy, and the learning-augmented algorithm uses constrained min-cost flow.

Significance. If fully established, the hardness result would be the first explicit inapproximability barrier for ℓ2^2 min-sum k-clustering, resolving a long-standing open question. The constants are explicit, and the conditional 1.327 factor is natural under the stated hypothesis. The PTAS significantly improves the dependency on n over previous n^{O(k/ε^2)} schemes, and the learning-augmented result provides a smooth tradeoff with oracle quality. The paper clearly identifies the new Balanced-JCH* hypothesis and gives explicit formulas for the hardness factors. However, the proof of the key balance property in Theorem 2.6 is only sketched, and one lemma in the PTAS section is not convincingly proven; these issues need to be addressed before the results can be considered fully established.

major comments (3)
  1. [§2.3, Theorem 2.6] The balanced completeness proof is incomplete. The text states the 1/2 ± O(δ) split only for hyperedges where the fixed vertex (vi,x) is the unique vertex from its layer (j > i). For hyperedges with j < i, the vertex lies on the two-vertex side; a direct computation from the same sampling procedure gives, conditional on the hyperedge containing (vi,x), approximately 1/4 with all three vertices in S, 1/4 with only (vi,x) in S, and 1/2 with exactly two vertices in S. This is not the claimed 1/2/1/2 split. The conclusion that a 2/3 ± O(δ)-balanced assignment exists does not follow from the stated calculation alone. This is load-bearing because Theorem 2.7's completeness bound requires |Ci| ≤ (1+δ)|E|/k, and the unconditional 1.056 hardness in Theorem 1.3 depends on Theorem 2.6. The claim may still be true (the two-vertex side actually gives a smaller assignment ratio, about 7/12), but the manuscript must supply the missing analysis for j < i.
  2. [§3, Lemma 3.9] The preprocessing lemma is not proven convincingly. The proof contains the garbled inequality '1/20 T · OPT ≤ 20n^2 · T', and the key claim that if two k-means centers satisfy ||c1−c2||^2 > n^8 T then no points from the corresponding k-means clusters can belong to the same optimal min-sum cluster is not justified. A point may be arbitrarily far from its assigned center, so two points could be close to each other even if their centers are far. This lemma underlies the bound on the number of distributions in Lemma 3.15 and hence the PTAS runtime claimed in Theorem 1.4; it needs a careful proof or a precise reference.
  3. [§2.2 and Theorem 1.3] The statement of Theorem 1.3 as unconditional NP-hardness is stronger than what the proof supports. The dense instances used for the unconditional bound come from Theorem 2.5, which is stated 'under randomized reductions'. If the density property and hence the 1.056 hardness rely on randomized reductions, the theorem statement should either say so explicitly or provide a derandomization. The current phrasing 'It is NP-hard to approximate' is potentially misleading.
minor comments (5)
  1. [§4, Theorem 4.4 and Theorem 1.5] The two cases for γα overlap: the first says α ∈ [0, 1/7], the second α ∈ [0, 1/2). The second formula is presumably intended for α ∈ [1/7, 1/2); please correct the interval.
  2. [§4, Lemma 4.6] The inequality '|P*_i| ≤ 1/(1−α) · |P*_i|' should read '|P*_i| ≤ 1/(1−α) · |P_i|'.
  3. [§2.3] The claim about the fraction of hyperedges with only (vi,x) in S is only meaningful for (vi,x) ∈ S; please state this explicitly.
  4. [§2.2.1] The line 'we aim at showing that the ℓ2^2 min-sum k-clustering cost of C is at least ((z − y) + 2(1 − α) − o(1))ℓ|P|' contains an undefined 'ℓ' and appears garbled; the final lower bound is in terms of 2|P|^2/k.
  5. [§3] The parameter β is set to Θ(ε^{-2}) in Lemma 3.5 but later to 2400/ε^2 in Lemma 3.11; the constants are not harmonized, which makes the exposition harder to follow.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness results are derived from a new reduction theorem and an explicitly stated hypothesis, not by assuming the target claim; the PTAS and learning-augmented results are self-contained.

full rationale

The paper's unconditional hardness (Theorem 1.3, factor 1.056) is derived from Theorem 2.7, whose proof is given in Section 2.2.1, combined with Theorem 2.6, which is proved in Section 2.3 by analyzing the [CKL22] PCP-to-hypergraph reduction. The soundness lemmas (Lemma 2.11 and Claim 2.8) and the starting NP-hardness (Theorem 2.5) are cited from [CKL22], a peer-reviewed paper with overlapping authorship, but they are external published results rather than assumptions equivalent to the present conclusion; the paper does not assume the 1.056 hardness. The conditional 1.327 bound is explicitly conditional on the new Balanced-JCH* hypothesis stated as Hypothesis 2.4, so it is a conditional theorem rather than a circular appeal. The PTAS (Theorem 1.4) and learning-augmented algorithm (Theorem 1.5) are proved from scratch in Sections 3 and 4 using standard facts from [IKI94] and [NCN23] and do not feed back into the hardness claim. The only notable concern is a terseness or correctness gap: the balanced-completeness proof in Section 2.3 asserts that 'an inspection of the sampling procedure reveals' the required 1/2 ± O(δ) split and then 'therefore, there must be an assignment' with 2/3 ± O(δ) loads, without a fully detailed derivation for both sides of each hyperedge. That is a potential unproven step, but it is not circular: the balanced assignment is claimed to be derived from the sampling procedure, not assumed as an input. Therefore no derivation reduces by construction to its own inputs.

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

The central results rest on standard PCP theorems, the authors' own JCH framework from [CKL22], the new Balanced-JCH* hypothesis (for the 1.327 bound), a near-linear k-means approximation [DSS24], and the LEARNED CENTERS black box [NCN23]. No physical entities are introduced; the only new postulated object is the Balanced-JCH* conjecture, listed as an axiom. The free parameters β, α, η, γα, and z are hand-chosen or inherited from hypotheses, not fitted to data.

free parameters (5)
  • β = β ≥ 2400/ε² (also 12/ε² in Lemma 3.5)
    Hand-chosen threshold defining the core Cβ_i; used throughout the PTAS analysis. Not fitted to data, but chosen to make Markov and sampling lemmas work.
  • α (PTAS parameter) = α ≤ ε/16
    Distortion parameter in the D2-sampling analysis (Lemma 3.10, Lemma 3.11). Chosen by hand.
  • η = absolute constant in runtime exponent (not explicit)
    Absorbs constants in Lemma 3.8 and Theorem 3.17; the paper states existence but does not compute it.
  • γα = 7.7 for α∈(0,1/7), else (5α-2α²)/((1-2α)(1-α))
    Guarantee of the LEARNED CENTERS algorithm from [NCN23], used as a black box in Section 4.
  • z = exists per Balanced-JCH*, not explicit
    The conditional hardness assumes z exists for each ε; the reduction's gap depends on z, but the statement is for the optimal factor over z.
assumptions (6)
  • ad hoc to paper Balanced-JCH*: for every ε>0 there is z=z(ε) such that (1-1/e+ε, z, z-1, 0)-Balanced Johnson Coverage* is NP-hard.
    New unproven hypothesis stated as Hypothesis 2.4; drives the 1.327 conditional hardness.
  • standard math Multilayered PCP theorem of Dinur-Guruswami-Khot-Regev and Khot.
    Used to prove Theorem 2.6, the balanced special case of Balanced-JCH*.
  • domain assumption The reduction and soundness of [CKL22] from multilayered PCPs to 3-hypergraph vertex coverage (Lemma 2.11).
    Theorem 2.6 takes this reduction 'verbatim' and adds completeness/regularity analysis; soundness is cited, not reproven.
  • domain assumption There is a near-linear time 20-approximation for k-means ([DSS24]).
    Used in Lemma 3.9 to preprocess points and bound inter-point distances; cited from prior work.
  • domain assumption LEARNED CENTERS guarantee for learning-augmented k-means ([NCN23], Theorem 4.4).
    Black box used in Section 4 for the learning-augmented result.
  • standard math Mean identities (Fact 4.1, Fact 4.2) and total unimodularity of flow LPs (Theorem 4.8, 4.10).
    Standard results from [IKI94] and [Sch98].

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Approximability of $\ell_2^2$ Min-Sum Clustering." pith.science (2026). https://pith.science/paper/HPU3CUSO

@misc{pith2026241203332,
  author       = {Pith},
  title        = {Pith review of: On Approximability of $\ell_2^2$ Min-Sum Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HPU3CUSO}},
  note         = {Machine review of arXiv:2412.03332}
}
abstract

The $\ell_2^2$ min-sum $k$-clustering problem is to partition an input set into clusters $C_1,\ldots,C_k$ to minimize $\sum_{i=1}^k\sum_{p,q\in C_i}\|p-q\|_2^2$. Although $\ell_2^2$ min-sum $k$-clustering is NP-hard, it is not known whether it is NP-hard to approximate $\ell_2^2$ min-sum $k$-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the $\ell_2^2$ min-sum $k$-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than $1.056$ and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a nearly linear time parameterized PTAS for $\ell_2^2$ min-sum $k$-clustering running in time $O\left(n^{1+o(1)}d\cdot \exp((k\cdot\varepsilon^{-1})^{O(1)})\right)$, where $d$ is the underlying dimension of the input dataset. Finally, we consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label $i\in[k]$ for input point, thereby implicitly partitioning the input dataset into $k$ clusters that induce an approximately optimal solution, up to some amount of adversarial error $\alpha\in\left[0,\frac{1}{2}\right)$. We give a polynomial-time algorithm that outputs a $\frac{1+\gamma\alpha}{(1-\alpha)^2}$-approximation to $\ell_2^2$ min-sum $k$-clustering, for a fixed constant $\gamma>0$.

Figures

Figures reproduced from arXiv: 2412.03332 by the authors.

Figure 1
Figure 1. Clustering of input dataset in Figure 1a with k = 2. Figure 1b is an optimal centroid-based clustering, e.g., k-median or k-means, while the more natural clustering in Figure 1c is an optimal density-based clustering, e.g., ℓ2 min-sum k-clustering. based on the geometry of the underlying space; the only known lower bound is the NP-hardness of the problem [ADHP09, BOR21, AKP24]. Thus a fundamental open question is: Q… view at source ↗
Figure 2
Figure 2. Note that with arbitrarily small error rate, i.e., [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Examples of input instances of the Johnson Coverage Hypothesis for [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Constrained min-cost flow problem Lemma 4.5. Let F be the cost of the flow output by Algorithm 2. Then for the corresponding clustering Q1, . . . , Qk output by Algorithm 2, we have 1 2 ∑ i∈[k] ∑ xu,xv∈Qi ∥xu − xv∥ 2 2 ≤ F. Proof. Let S be any flow output by Algorithm …
Figure 5
Figure 5. Figure 5: Example of transformation of capacitated min-cost flow problem into uncapacitated min-cost [PITH_FULL_IMAGE:figures/full_fig_p038_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Learning-Augmented Hierarchical Clustering

    cs.DS 2025-06 conditional novelty 7.0 of 10

    With a noisy oracle that says which of three points splits off first, hierarchical clustering achieves constant approximation for Dasgupta and near-optimal Moseley-Wang, bypassing known hardness.

Reference graph

Works this paper leans on

90 extracted references · 48 canonical work pages · cited by 1 Pith paper

  1. [1]

    Online metric algorithms with untrusted predictions

    Antonios Antoniadis, Christian Coester, Marek Eli \' a s, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms , 19(2):19:1--19:34, 2023

    2023

  2. [2]

    Chen, and Piotr Indyk

    Anders Aamand, Justin Y. Chen, and Piotr Indyk. (optimal) online bipartite matching with degree information. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS , 2022

    2022

  3. [3]

    Np-hardness of euclidean sum-of-squares clustering

    Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. Np-hardness of euclidean sum-of-squares clustering. Mach. Learn. , 75(2):245--248, 2009

    2009

  4. [4]

    Online algorithms with multiple predictions

    Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference on Machine Learning, ICML , pages 582--598, 2022

    2022

  5. [5]

    Enver Aman, Karthik C. S. , and Sharath Punna. On connections between k-coloring and Euclidean k-means. In 32nd Annual European Symposium on Algorithms, ESA 2024 , 2024. To appear

    2024

  6. [6]

    Inapproximability of vertex cover and independent set in bounded degree graphs

    Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput. , 7(1):27--43, 2011

    2011

  7. [7]

    Online graph algorithms with predictions

    Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 35--66, 2022

    2022

  8. [8]

    k-means++: the advantages of careful seeding

    David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007 , pages 1027--1035. SIAM , 2007

    2007

Show all 90 references
  1. [9]

    Finding low error clusterings

    Maria - Florina Balcan and Mark Braverman. Finding low error clusterings. In COLT 2009 - The 22nd Conference on Learning Theory , 2009

    2009

  2. [10]

    Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma

    Luca Becchetti, Marc Bury, Vincent Cohen - Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC ,...

    2019

  3. [11]

    Approximate clustering without the approximation

    Maria - Florina Balcan, Avrim Blum, and Anupam Gupta. Approximate clustering without the approximation. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1068--1077, 2009

    2009

  4. [12]

    Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds

    Nikhil Bansal, Vincent Cohen - Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. CoRR , abs/2405.01339, 2024

    2024 arXiv

  5. [13]

    Approximating min-sum k-clustering in metric spaces

    Yair Bartal, Moses Charikar, and Danny Raz. Approximating min-sum k-clustering in metric spaces. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing , pages 11--20, 2001

    2001

  6. [14]

    Salavatipour, and Rohit Sivakumar

    Babak Behsaz, Zachary Friggstad, Mohammad R. Salavatipour, and Rohit Sivakumar. Approximation algorithms for min-sum k-clustering and balanced k-median. Algorithmica , 81(3):1006--1030, 2019

    2019

  7. [15]

    The primal-dual method for learning augmented algorithms

    \' E tienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  8. [16]

    Min-sum clustering (with outliers)

    Sandip Banerjee, Rafail Ostrovsky, and Yuval Rabani. Min-sum clustering (with outliers). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 16:1--16:16, 2021

    2021

  9. [17]

    Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P

    Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In The Tenth International Conference on Learning Repr...

    2022

  10. [18]

    Chen, Piotr Indyk, and Tal Wagner

    Justin Y. Chen, Piotr Indyk, and Tal Wagner. Streaming algorithms for support-aware histograms. In International Conference on Machine Learning, ICML , pages 3184--3203, 2022

    2022

  11. [19]

    Vincent Cohen - Addad and Karthik C. S. Inapproximability of clustering in lp metrics. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 519--539, 2019

    2019

  12. [20]

    Vincent Cohen - Addad, Karthik C. S. , and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 2635--2648, 2021

    2021

  13. [21]

    Vincent Cohen - Addad, Karthik C. S. , and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in _p -metrics. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1493--1530, 2022

    2022

  14. [22]

    Cohen, Yin Tat Lee, and Zhao Song

    Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. J. ACM , 68(1):3:1--3:39, 2021

    2021

  15. [23]

    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 Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS , 2022

    2022

  16. [24]

    Computer science 590, lecture notes

    Vincent Conitzer. Computer science 590, lecture notes. https://courses.cs.duke.edu/fall12/compsci590.1/network_flow.pdf, 2012

    2012

  17. [25]

    Sublinear-time approximation algorithms for clustering via random sampling

    Artur Czumaj and Christian Sohler. Sublinear-time approximation algorithms for clustering via random sampling. Random Struct. Algorithms , 30(1-2):226--256, 2007

    2007

  18. [26]

    A new coreset framework for clustering

    Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 169--182, 2021

    2021

  19. [27]

    Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang

    Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML , pages 3583--3602, 2022

    2022

  20. [28]

    Woodruff, and Samson Zhou

    Vincent Cohen - Addad, David P. Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log n) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 883--908, 2023

    2023

  21. [29]

    A new multilayered PCP and the hardness of hypergraph vertex cover

    Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. , 34(5):1129--1146, 2005

    2005

  22. [30]

    Faster matchings via learned duals

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 10393--10406, 2021

    2021

  23. [31]

    A randomized approximation scheme for metric MAX-CUT

    Wenceslas Fernandez de la Vega and Claire Kenyon. A randomized approximation scheme for metric MAX-CUT . J. Comput. Syst. Sci. , 63(4):531--541, 2001

    2001

  24. [32]

    Approximation schemes for clustering problems

    Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing , pages 50--58, 2003

    2003

  25. [33]

    Predictive flows for faster ford-fulkerson

    Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster ford-fulkerson. In International Conference on Machine Learning, ICML , volume 202, pages 7231--7248, 2023

    2023

  26. [34]

    Settling time vs

    Andrew Draganov, David Saulpic, and Chris Schwiegelshohn. Settling time vs. accuracy tradeoffs for clustering big data. Proc. ACM Manag. Data , 2(3):173, 2024

    2024

  27. [35]

    Ergun, Zhili Feng, Sandeep Silwal, David P

    Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented k -means clustering. In The Tenth International Conference on Learning Representations, ICLR , 2022

    2022

  28. [36]

    Derandomized dimensionality reduction with applications

    Lars Engebretsen, Piotr Indyk, and Ryan O'Donnell. Derandomized dimensionality reduction with applications. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 705--712, 2002

    2002

  29. [37]

    A threshold of ln n for approximating set cover

    Uriel Feige. A threshold of ln n for approximating set cover. J. ACM , 45(4):634--652, 1998

    1998

  30. [38]

    Schulman

    Dan Feldman and Leonard J. Schulman. Data reduction for weighted and outlier-resistant clustering. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 1343--1354. SIAM , 2012

    2012

  31. [39]

    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

  32. [40]

    Approximation algorithms for min-sum p-clustering

    Nili Guttmann - Beck and Refael Hassin. Approximation algorithms for min-sum p-clustering. Discret. Appl. Math. , 89(1-3):125--142, 1998

    1998

  33. [41]

    Embeddings and non-approximability of geometric problems

    Venkatesan Guruswami and Piotr Indyk. Embeddings and non-approximability of geometric problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 537--538, 2003

    2003

  34. [42]

    Learning-augmented algorithms for online linear and semidefinite programming

    Elena Grigorescu, Young - San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning-augmented algorithms for online linear and semidefinite programming. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, ...

    2022

  35. [43]

    Online algorithms for rent-or-buy with expert advice

    Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML , pages 2319--2327, 2019

    2019

  36. [44]

    Learning-based frequency estimation algorithms

    Chen - Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR , 2019

    2019

  37. [45]

    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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC , pages 1594--1604, 2024

    2024

  38. [46]

    Min sum clustering with penalties

    Refael Hassin and Einat Or. Min sum clustering with penalties. Eur. J. Oper. Res. , 206(3):547--554, 2010

    2010

  39. [47]

    Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 1416--1429, 2020

    2020

  40. [48]

    Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract)

    Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In Proceedings of the Tenth Annual Symposium on Computational Geometry , pages 332--339, 1994

    1994

  41. [49]

    Online knapsack with frequency predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 2733--2743, 2021

    2021

  42. [50]

    A sublinear time approximation scheme for clustering in metric spaces

    Piotr Indyk. A sublinear time approximation scheme for clustering in metric spaces. In 40th Annual Symposium on Foundations of Computer Science, FOCS , pages 154--159, 1999

    1999

  43. [51]

    Learning-based low-rank approximations

    Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS , pages 7400--7410, 2019

    2019

  44. [52]

    Woodruff

    Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. Learning-augmented data stream algorithms. In 8th International Conference on Learning Representations, ICLR , 2020

    2020

  45. [53]

    Shaofeng H. - C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In The Tenth International Conference on Learning Representations, ICLR , 2022

    2022

  46. [54]

    Liu, and Aaron Sidford

    Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, F...

    2023

  47. [55]

    Data clustering: a review

    Anil K Jain, M Narasimha Murty, and Patrick J Flynn. Data clustering: a review. ACM computing surveys (CSUR) , 31(3):264--323, 1999

    1999

  48. [56]

    A faster algorithm for solving general lps

    Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 823--832, 2021

    2021

  49. [57]

    A new polynomial-time algorithm for linear programming

    Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Comb. , 4(4):373--396, 1984

    1984

  50. [58]

    Chi, Jeffrey Dean, and Neoklis Polyzotis

    Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference , pages 489--504, 2018

    2018

  51. [59]

    Learning predictions for algorithms with predictions

    Misha Khodak, Maria - Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS , 2022

    2022

  52. [60]

    Hardness results for coloring 3 -colorable 3 -uniform hypergraphs

    Subhash Khot. Hardness results for coloring 3 -colorable 3 -uniform hypergraphs. In 43rd Symposium on Foundations of Computer Science (FOCS ), Proceedings , pages 23--32, 2002

    2002

  53. [61]

    On the hardness of approximating max k-cut and its dual

    Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. On the hardness of approximating max k-cut and its dual. Chic. J. Theor. Comput. Sci. , 1997

    1997

  54. [62]

    Kleinberg

    Jon M. Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, NIPS , pages 446--453, 2002

    2002

  55. [63]

    James R. Lee. Spectral hypergraph sparsification via chaining. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 207--218. ACM , 2023

    2023

  56. [64]

    Woodruff

    Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David P. Woodruff. Learning the positions in countsketch. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  57. [65]

    Online scheduling via learned weights

    Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1859--1877, 2020

    2020

  58. [66]

    Woodruff

    Honghao Lin, Tian Luo, and David P. Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, ICML , pages 13431--13440, 2022

    2022

  59. [67]

    Efficient inverse maintenance and faster algorithms for linear programming

    Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS , pages 230--249, 2015

    2015

  60. [68]

    Improved and simplified inapproximability for k-means

    Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett. , 120:40--43, 2017

    2017

  61. [69]

    Solving empirical risk minimization in the current matrix multiplication time

    Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory, COLT , pages 2140--2157, 2019

    2019

  62. [70]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM , 68(4):24:1--24:25, 2021

    2021

  63. [71]

    On approximate geometric k-clustering

    Jir \' Matousek. On approximate geometric k-clustering. Discret. Comput. Geom. , 24(1):61--84, 2000

    2000

  64. [72]

    A model for learned bloom filters and optimizing by sandwiching

    Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 462--471, 2018

    2018

  65. [73]

    Varadarajan

    Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci. , 442:13--21, 2012

    2012

  66. [74]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms , pages 646--662. Cambridge University Press, 2020

    2020

  67. [75]

    Thy Dinh Nguyen, Anamay Chaturvedi, and Huy L. Nguyen. Improved learning-augmented algorithms for k-means and k-medians clustering. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  68. [76]

    Approximation schemes for min-sum k-clustering

    Ismail Naderi, Mohsen Rezapour, and Mohammad R Salavatipour. Approximation schemes for min-sum k-clustering. Discrete Optimization , 54:100860, 2024

    2024

  69. [77]

    Improving online algorithms via ML predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS , pages 9684--9693, 2018

    2018

  70. [78]

    Papadimitriou and Mihalis Yannakakis

    Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. , 43(3):425--440, 1991

    1991

  71. [79]

    Theory of linear and integer programming

    Alexander Schrijver. Theory of linear and integer programming . John Wiley & Sons, 1998

    1998

  72. [80]

    Schulman

    Leonard J. Schulman. Clustering for edge-cost minimization (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , pages 547--555, 2000

    2000

  73. [81]

    Gonzalez

    Sartaj Sahni and Teofilo F. Gonzalez. P-complete approximation problems. J. ACM , 23(3):555--565, 1976

    1976

  74. [82]

    Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis

    Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung - Chan An. Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In International Conference on Machine Learning, ICML , pages 31539--31561, 2023

    2023

  75. [83]

    Goodfellow, and Rob Fergus

    Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR , Conference Track Proceedings , 2014

    2014

  76. [84]

    Pravin M. Vaidya. Speeding-up linear programming using fast matrix multiplication. In 30th Annual Symposium on Foundations of Computer Science , pages 332--337, 1989

    1989

  77. [85]

    Pravin M. Vaidya. An algorithm for linear programming which requires o(((m+n)n\( ^ 2 \) + (m+n)\( ^ 1.5 \)n)l) arithmetic operations. Math. Program. , 47:175--201, 1990

    1990

  78. [86]

    Online algorithms for multi-shop ski rental with machine learned advice

    Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  79. [87]

    Optimal robustness-consistency trade-offs for learning-augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  80. [88]

    Woodruff, Peilin Zhong, and Samson Zhou

    David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding window model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS , 2023

    2023

  81. [89]

    Survey of clustering algorithms

    Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions on neural networks , 16(3):645--678, 2005

    2005

  82. [90]

    Space complexity of euclidean clustering

    Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space complexity of euclidean clustering. In 40th International Symposium on Computational Geometry, SoCG , pages 82:1--82:16, 2024

    2024

Pith tools

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