Source-linked AI summary
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
TL;DR
Metric k-minsum clustering is a density-based objective whose computational complexity is less understood than that of center-based criteria. The paper combines adaptive sampling and enumeration into a sublinear-time approximation scheme, while proving conditional barriers for related k-median problems. It thereby establishes a separation between these problems in the sublinear regime.
Problem
Metric k-minsum clustering remains less understood computationally than center-based clustering, and its metric setting lacks the natural cluster centers used by related approaches.
Source: §1 · pp. 2, 4Method
The algorithm uses adaptive non-uniform sampling, enumerates cluster proxies and approximate sizes and costs, and applies sublinear-time metric MAX k-CUT approximation.
Source: §1 · p. 6Results
n1+o(1)·22O(k log(k/ε)) operations give a (1+ε)-approximation for k-minsum, while SETH rules out n2−ε-time distinction between balanced 2-median costs ≤m and ≥(1+δ)m.
Source: §1 · pp. 2–3Takeaways & Limitations
For k=o(log log n/log log log n) at constant ε, k-minsum is sublinear-time approximable, unlike the closely related k-median problems that likely resist similar algorithms.
Source: §1 · pp. 3, 8The approach does not currently yield a fixed-parameter tractable coreset because a core’s center of mass may not approximate the entire cluster’s center of mass.
Source: §1 · p. 5
Abstract
from arXiv · showhide
Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.
1 Introduction
Metric k-minsum clustering lacks the center-based structure that has made related clustering problems easier to approximate. The paper gives a fixed-parameter approximation scheme that is sublinear for mildly increasing k, alongside conditional lower bounds for k-median variants.
1 Introduction
- n1+o(1)·22O(k log(k/ε)) arithmetic operations suffice for a (1+ε)-approximation, and the algorithm is sublinear for k=o(log log n/log log log n) when ε is constant.The running-time bound assumes that computing a pairwise distance is one operation.Source: §1 · p. 2
- The result improves on an older scheme whose polynomial dependence on n degrades with k, extending sublinear-time approximation to mildly increasing k.For constant ε, the earlier scheme is polynomial-time only when k is constant, whereas this algorithm is sublinear for k=o(log log n/log log log n).Source: §1 · p. 2
- Under SETH, no n2−ε-time algorithm distinguishes balanced 2-median instances with cost at most m from those with cost at least (1+δ)m.The lower bound uses m=Oε(log n) clients; in certain parameter ranges, the input has npolylog(n) distances, so even quadratic time may be necessary.Source: §1 · p. 3
- Metric k-minsum clustering lacks a natural center whose properties support the efficient center approximation used in squared-Euclidean k-minsum and k-means.The paper notes that a metric cluster’s median neither is easily approximated nor approximates the minsum objective well.Source: §1 · p. 4
- Adaptive non-uniform sampling generates candidates that can hit large and small clusters, while proxy and approximate size-and-cost enumeration supports assigning points to cluster unions.Assigning outliers requires a cross-cluster charging argument because outliers can mix with smaller clusters’ cores.Source: §1 · p. 5
- The running time depends on controlling candidate clusterings, efficiently assigning points, and sublinear approximation schemes for metric MAX k-CUT and minsum-cost estimation.The paper’s metric MAX k-CUT scheme is a new sublinear-time building block, improving on a previously known linear-time scheme.Source: §1 · pp. 3, 6
- The lower-bound proof adapts the Distributed PCP framework through gap maxcoverage instances and a reduction to clustering instances.The paper applies this approach to conditional subquadratic approximation lower bounds for center-based objectives including 2-median and balanced 2-median.Source: §1 · p. 6
- Minsum clustering can capture irregular, non-convex, or overlapping clusters that a single centroid does not represent well.The paper contrasts the natural partition of two concentric rings with the unnatural hyperplane split produced by k-means and k-median.Source: §1 · p. 6
2 The Approximation Scheme
This section develops the approximation scheme through candidate-center generation, assignment of far and close points, and cluster-cost estimation. It also presents the sublinear-time approximation algorithm for metric MAX k-CUT used to resolve close-point conflicts.
2.1 Preliminaries
- The W1 transportation norm embeds point distances isometrically, and a point’s distance to a cluster’s uniform distribution equals its average distance to the cluster.The cluster quantity ΔC is defined as the average of these distances over points in C.Source: §2.1 · pp. 8–9
2.2 Overview
- The four-stage scheme runs in time dominated by n^(1+o(1)) · 2^(2O(k log(k/ε))), using center generation, far-point assignment, close-point assignment, and cost estimation.The close-point stage uses a sublinear-time approximation scheme for metric MAX h-CUT within components of neighboring clusters.Source: §2.2 · pp. 9, 11
- For any k-clustering, randomized center generation outputs at most (n/ε)^o(1) + 2^(O(k log k)) candidate sets, one of which covers every cluster with probability at least 1 − δ.Each set contains at most η · (k^2/ε) · log(k/δ) points; the algorithm runs in (n^(1+o(1)) + 2^(O(k log k))) · ((k/ε) · log(1/δ))^(O(1)) time.Source: §2.2 · p. 10
- Theorem 6 produces partial clusterings assigning all far points, with at least one assignment extendable to a clustering of controlled cost under Hypothesis 1.The supplied theorem passage truncates the cost bound, so its approximation factor cannot be stated here.Source: §2.2 · p. 11
- A randomized algorithm completes a partial assignment satisfying Theorem 6’s guarantee to a (1 + ε)-approximate clustering in time n · 2^(O(k log(k/ε))) · log(n/δ) + 2^(2O(k log(k/ε))).The guarantee assumes Hypothesis 1 for the extended clustering.Source: §2.2 · p. 11
2.3 Center Approximation
- The center-approximation algorithm grows a depth-(k − 1) tree, augmenting candidate points through distance-proportional sampling to proxy cluster cores.Uniform initialization and adaptive sampling support the covering guarantee; the analysis establishes substantial sampling probability for the core of the largest uncovered cluster.Source: §2.3 · pp. 13, 14, 17
- 1−δ probability suffices to obtain a leaf whose center set (ε,5)-covers all clusters; the tree has (10 log(nk/ε))^(k−1) leaves.Each internal node samples 1200·(k/ε)·ln(k/δ) points; when k=o(log(n/ε)/log log(n/ε)), the number of leaves is (n/ε)^o(1), and otherwise it is 2^O(k log k).Source: §2.3 · p. 19
2.4 Assignment of Far Points
- The far-point assignment minimizes point costs via an integral network flow, subject to per-pattern capacity constraints, and the output commits far points while restricting other assignments to clusters where they are not β−7-far.The algorithm uses approximate cardinalities for the capacity bounds; the partial clustering is analyzed through an extension to a full clustering.Source: §2.4 · p. 21
- The analysis establishes that D is near-optimal and compares the cost of its full-clustering extension C′ with the cost of D.The stated proof plan uses Lemma 13 for D’s near-optimality and Lemma 15 to bound C′’s cost relative to D.Source: §2.4 · p. 21
- At most β·|Ci| points in any cluster Ci are β−1-far for that cluster.The claim follows using the approximate center and cluster-size estimates with Markov’s inequality.Source: §2.4 · pp. 21–22
- At least one of at most n^{o(1)}·2^{2O(k log(k/ε))} partial clusterings can be extended to satisfy Lemma 15, and the enumeration runs in n^{1+o(1)}·2^{2O(k log(k/ε))} time.The assignment computation groups interchangeable points into buckets and uses minimum-cost flow.Source: §2.4 · pp. 34–35
2.5 Assignment of Close Points
- The close-point procedure yields a clustering of cost at most (1 + ε/k)·OPT, then MAX |V(K′)|-CUT approximations give a k-minsum solution within ε·OPT of that cost.Its running time is (k/ε)^{O(k)}·n·log(n/δ) + 2(k/ε)^{O(k)}.Source: §2.5 · pp. 38–39
2.6 A Sublinear Algorithm for Metric MAX k-CUT
- A randomized algorithm computes a (1 − ε)-approximation to the optimal metric MAX k-CUT solution in time O(ε^-2·n·log(n/δ)) + O(ε^-3·n·k^4) + k^{O(ε^-2)}, where δ is the failure probability.Source: §2.6 · p. 39
- The MAX k-CUT algorithm achieves additive error less than 10·ε·OPT in running time O(ε^-3·n·k^4) + k^O(ε^-2); repeated rounding instances may obtain the desired error with high probability.The fractional cut can be rounded into a true cut.Source: §2.6 · p. 42
2.7 Computing the Cost of a Cluster
- A randomized weighted sample of O(ε^-2·log(|B|/δ)) points estimates distances from every p∈B to A with probability at least 1−δ.The method samples according to a distribution based on distances to a proxy median of A.Source: §2.7 · p. 43
- For a cluster X, a weighted sample estimates its pairwise-distance cost within (1±ε) with probability at least 1−δ in O(|X|·ε^-2·log δ^-1) time.The estimate evaluates sampled points’ distances to the cluster’s mean vector.Source: §2.7 · p. 44
3 Conditional Lower Bounds
This section proves conditional lower bounds for balanced 2-median and parameterized k-minsum, using SETH- and Gap-ETH-based reductions.
3.1 Preliminaries
- The preliminary assumptions include SETH for k-SAT and Gap-ETH for bounded-occurrence 3-SAT.The section uses these hypotheses in its conditional lower bounds.Source: §3.1 · p. 44, §3 · p. 44
3.2 SETH Based Lower Bound for Balanced 2-Median
- Assuming SETH, for every ε>0 there exist δ(ε)>0 and c(ε) such that no n^(2−ε)-time algorithm distinguishes instances over |U|=c·log n with an equipartition having U1⊆Si from cases where every pair covers at most (1−δ)|U|.Source: §3.2 · p. 46
- Under SETH, the paper proves a subquadratic lower bound for 2-median and balanced 2-median with n facilities and Oε(log n) clients; the result also applies to 2-means.The formal theorem concerns distinguishing specified completeness and soundness cases.Source: §3.2 · pp. 47–48
- The reduction maps a set system to facilities and clients so that a covered equipartition yields cost |U|, while a MaxCover gap supports a subquadratic-time contradiction.The construction takes O(n·|U|) time, and the resulting algorithm would decide the MaxCover instance in subquadratic time.Source: §3.2 · p. 48
3.3 Parameterized Lower Bound from Gap-ETH for Min-Sum
- Gap-ETH would be false if metric k-minsum had a (1 + ε)-approximation running in 2^{o(k/ε)} · 2^{o(n)} time.The theorem rules out such an algorithm unless Gap-ETH fails.Source: §3.3 · p. 49
- Triangle-packing instances become n-point metrics with edge distances 1 and nonedge distances 2; a perfect packing gives k = n/3 and clustering cost n.The construction and a hypothetical solver would decide the gap triangle-packing instance in 2^{o(n)} time.Source: §3.3 · pp. 49–50