WorksComputer Science
Tight Coreset Bounds for Euclidean -Clustering
Abstract
We study the optimal coreset size for Euclidean -clustering, where is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of for , matching the known upper bound up to polylogarithmic factors. For , the upper bound remained unmatched. The previous lower bounds gave only . We close this gap by proving a matching lower bound throughout , including arbitrarily small . Together with known bounds, this determines the optimal worst-case coreset size as for every integer and . In particular, the bounds are for -median when , and for -means when . Our construction uses projection levels to encode four-wise independent signs, allowing centers to detect omissions regardless of how the retained points are reweighted.
Introduction
We study the optimal coreset size for Euclidean -clustering, where is a fixed constant.
-clustering.
Given a finite dataset and an integer , the goal is to find a set of centers minimizing
This includes two classical clustering problems: -median (), which minimizes the sum of distances to the nearest center, and -means (), which minimizes the sum of squared distances. These objectives are widely used to represent a dataset by a small set of centers and have been extensively studied in data analysis, machine learning, and approximation algorithms [6].
Coresets.
For large datasets, coresets provide a way to reduce the input size while preserving the clustering objective [8, 9].
Definition 1.1 (Coreset). For , an -coreset for -clustering of is a subset with weights such that
where .
A clustering algorithm can therefore run on a coreset instead of the full dataset while retaining nearly the same approximation guarantee. A smaller coreset reduces the amount of data processed by the algorithm. This has motivated a long line of work on clustering coresets in Euclidean, doubling, and graph metrics [8, 9, 20, 18, 19].
Determining the optimal coreset size in Euclidean space is a central question in this literature. Cohen-Addad, Saulpic, and Schwiegelshohn [5] described improving the Euclidean bounds as arguably “the most important open problem in coresets.” Despite substantial progress on constructions independent of the dimension, matching the dependence on and has remained difficult.
Cohen-Addad et al. [10] proved an lower bound and dimension-independent upper bounds. Subsequent work obtained upper bounds of for -median and for -means [11].1 These results left open whether the superlinear dependence on was necessary, or whether coresets of size always existed.
Huang, Li, and Wu [6] ruled out the latter possibility. They proved a lower bound of for , matching the known upper bound up to polylogarithmic factors. They also proved the upper bound for every fixed , extending the preceding bounds for -median and -means.
The bounds still did not match for . In the range , Huang, Li, and Wu also proved the stronger lower bound . Below , the earlier bound was stronger. Neither matched throughout , leaving the following question open:
Is the optimal coreset size for every ?
Our Contributions
We answer this question affirmatively, including for arbitrarily small .
Theorem 1.2 (Coreset lower bound). For every fixed real , every integer , and every , there exist an integer and a finite dataset such that every -coreset for -clustering of has size
For -means, the previous lower bounds are for and for . At , we improve the bound from [6] to ; at , we improve it from [10] to . These are improvements by factors of and , respectively, up to polylogarithmic factors.
Combining Theorem 1.2 with the known bounds [10, 6] gives the following characterization.
Corollary 1.3 (Optimal coreset size). For every fixed real , integer , and , the optimal worst-case coreset size for Euclidean -clustering, over datasets of unrestricted dimension, is
Technical Overview
We explain the lower bound for -means when , then extend the argument to general .
Revisiting the previous lower-bound construction.
At , Huang, Li, and Wu [6] construct points in far-apart copies . Within each copy, indexes spheres and labels offsets. Suppressing , the local points are
where is a coordinate direction, is sphere ’s center, and is a unit offset. Each copy has spheres and almost orthogonal offsets. Each offset occurs on spheres, at most once per sphere, giving points per copy.
Suppose a putative coreset retains at most half the dataset. Choose an active copy with , where . The query uses one center for all occurrences of in . The term turns a constant change in ’s -coordinate into a cost change on sphere . The other coordinates keep the center norms and fixed; the offset design preserves nearest-center assignments. Thus
The cost difference can be reversed. The other copies use their sphere centers, at unit squared cost per point, and all centers together fit within the budget [6 Claim 2.2].
A distant-center query forces [6 Claim 2.1]. Orienting the cost difference to avoid cancellation with the inactive error gives absolute error . Since the active and total costs are both , the relative error is at least
This proves the bound for a sufficiently small constant in : one center controls an offset’s occurrences on many spheres.
Failed attempts.
Below , the target polynomial size exceeds . Repeating each point times gives a multiset of size and suggests the required error scale. Draw uniform samples with replacement. Each location’s count has mean and standard deviation . An active copy has locations with cost differences of order , while the total cost is of order . This suggests
Equating this expression to gives . But the calculation only motivates the scale: one representative of weight at each location preserves every query cost exactly, so sampling fluctuations cannot rule out arbitrary reweighting.
A second attempt replaces by distinct offsets :
One center per replacement requires active centers, exceeding as grows. If instead the offsets with share across spheres, their distance to that center contains the common term
Changing cannot reproduce the costs and for retained and omitted replacements in the same group while the other distance terms remain fixed. A common cost change on this group changes the coreset error by that amount times , with on omitted points. The replacements must therefore admit groupings using few centers that detect these aggregate discrepancies despite arbitrary reweighting. We state the required properties next.
Identifying the properties needed from the new offsets.
We keep equal-sized, far-apart copies. For any retaining at most half of the new dataset , choose an active copy with at least half its points omitted. We require:
Distinct replacements. Each label’s replacements on a sphere are distinct, preventing compression of repeated points into a single representative.
Few centers per grouping. Each label admits partitions into polylogarithmically many groups, with one center per group shared across spheres.
Balanced costs. Every query satisfies , so inactive costs do not dilute the active error.
Error under arbitrary reweighting. Some query has absolute coreset error , assuming only that at least half of is omitted, not half of each group.
The dataset and query family are fixed before ; only the active copy and witnessing query depend on it. With copies, P3 turns P4 into the relative-error scale suggested by repetition.
Constructing the dataset and sharing centers.
Keep for copies, for spheres, and for labels; indexes a label’s replacements. Take far-apart copies, each with spheres and labels. Now choose the to be orthonormal, and replace each label’s single offset by . The local configuration is
The , the , and the distinct unit vectors lie in three mutually orthogonal subspaces; the need not be mutually orthogonal. Every offset now occurs on every sphere. All triples are distinct, each at distance from its sphere center , so and , giving P1.
Fix and an active copy as above; use local coordinates for its points and query centers. Lemma 2.1 supplies the and a fixed family of directions with
Here is the level index of , and . We will construct one center serving all points of label and level across spheres. Inactive copies use their sphere centers, giving the budget
Thus a query needs active centers instead of . Changing changes the grouping without increasing this count. A fixed partition with equal costs within each sphere–label–level group could be compressed to one weighted representative per group. To ensure that some grouping detects omissions, Lemma 2.1 also makes unbiased four-wise independent signs for uniform . Their discrepancy guarantee, used below, is what rules out such compression across all queries.
Figure 1. Geometry of the active copy (; schematic sectional views). (a) Spheres centered at repeat the same offset groups. (b) Both labels on one enlarged sphere: black arrows show , colored solid arrows show in their perpendicular sections, and dashed arrows show , ending on the sphere of radius . Each same-colored pair forms a cell and shares the matching nearest center (diamond) across all spheres. We illustrate levels for . The two offset sections are shown in local three-dimensional frames; relative lengths and query-center positions are not to scale.
Realizing level costs with shared centers.
For signs , let contain the active centers, the inactive sphere centers, and remote centers padding the count to . The active costs are
where the are the baselines in Eq. (7), independent of . The sphere-axis component of is proportional to , encoding one sign per sphere without changing its norm when signs are reversed. The label component separates labels. For a point at level , the projection component and an orthogonal norm adjustment make a competing level incur the penalty . With grid spacing , this penalty dominates any change in the signed term. Claim 2.2 verifies that remains nearest for every , giving P2. Inactive points have squared cost , so the active and total costs are both , giving P3.
Defeating arbitrary reweighting with opposite queries.
Extend by zero to omitted points, and write . The queries and have identical baselines and inactive costs. Subtracting their signed errors gives
The common weighted costs cancel exactly, without any bound on the retained weights. For each fixed , choose to match the sign of its inner sum. Lemma 2.1 then supplies one common direction with
For the last inequality, each omitted point contributes to a squared discrepancy. Each -point group’s norm is at least its number of omissions divided by , and omits at least half its points. Only the sum must be large for the common direction; different groups need not attain their maxima there.
The opposite queries therefore have signed errors differing by . At least one query has absolute error at least half this difference. Dividing by its true cost yields relative error . For , this proves P4 and recovers the scale suggested by repetition, now for every reweighting. Proposition 2.3 formalizes this argument.
Choosing parameters to obtain the lower bound.
The center budget permits and ; the relative error exceeds when is sufficiently small. In the principal range, Lemma 2.5 meets these requirements with
Every coreset must retain more than half these points, proving the lower bound.2
Extension to a general power .
For , raising Eq. (1) to produces a level-dependent difference between opposite queries. Since changes with , the coefficient of in the error sum would vary with the direction. The discrepancy lemma requires fixed coefficients; constant-factor estimates cannot substitute for equality in this signed sum.
Choose a sphere-axis displacement for each level so that
Readjusting the orthogonal center component preserves . Monotonicity and the mean value theorem allow this calibration within the displacement bound that preserves assignments; see § 2.5. The powered-cost difference is now a fixed coefficient times , so the same discrepancy argument applies.
An active point costs . Using copies, each with spheres, preserves the cost balance and uses inactive centers. The relative-error scale remains . Hence taking , , , and gives
§ 2.6 completes the integer and boundary cases.
Other Related Work
Sharper bounds for clustering coresets.
Bansal et al. [7] showed that sensitivity sampling constructs Euclidean -means coresets of size . For instances with constant cost stability, the same algorithm achieves size without knowing the stability parameter. Beyond Euclidean spaces, Cohen-Addad et al. [13] developed a sharp VC-dimension-based analysis, obtaining improved -median coreset bounds, including for shortest-path metrics in planar graphs.
Coresets for constrained clustering.
Coresets for capacitated and fair clustering, as well as more general assignment constraints, have been studied extensively [2, 3, 12, 15, 1]. For Euclidean capacitated -clustering with fixed , Huang et al. [15] obtained coresets of size .3
Coresets for robust clustering.
Coresets for clustering with outliers have also received substantial attention [4, 15, 16, 17, 14]. For Euclidean -clustering with outliers and fixed , Huang et al. [14] obtained coresets of size , and an alternative bound of .
Optimal Euclidean lower bound
This section proves Theorem 1.2: for every integer , fixed real , and , we construct a finite unweighted instance such that every strong -coreset has size . With a different parameter choice, the same construction also recovers the known lower bound in the large-error regime . We first treat and , then extend the argument to general and the remaining error range.
The proof combines a geometric construction, Proposition 2.3, and the parameter choice in Lemma 2.5. We first form a dataset from well-separated copies of the same point set. Any weighted subset containing at most half of the data points must omit at least half of the points in one copy. In that copy, we use two query center sets with opposite perturbations: their nearest-center assignments agree, while subtracting their signed errors cancels all terms independent of the perturbations. Optimizing the perturbation signs and then applying a discrepancy lemma yields a common projection direction with a large error gap, regardless of the retained weights. Finally, we choose the parameters so that the center budget is respected and at least one query violates the coreset guarantee.
Construction of the dataset
We follow the far-apart-copy framework of [6], in which each copy contains points on spheres centered along coordinate axes. Our construction splits each offset into two orthogonal components and uses one of them to group the points more finely. Let be integer parameters to be chosen later. For now, assume that , as required by Lemma 2.1; we verify this condition when choosing the parameters. The dataset , where , consists of sufficiently separated translates of the set
Here and are orthonormal bases of mutually orthogonal subspaces and . The distinct unit vectors lie in a third orthogonal subspace ; fix them, together with the set , as supplied by Lemma 2.1 below. We reserve the remaining dimension, with unit vector , for adjusting center norms. Thus is the Cartesian product, embedded in orthogonal subspaces, of , , and . The three orthogonal projections recover , , and , respectively, so different triples give different points. Consequently, and .
For each point in the th group, .
Thus, in local coordinates, each copy lies on spheres of radius , centered at for . The th sphere contains the points , indexed by and . Our queries will incur squared cost per point in one copy, to be designated the active copy later; using copies keeps this contribution of order . The following lemma supplies vectors with few projection levels and a common discrepancy witness. We will later apply it to the coreset weight discrepancies within the active copy.
Lemma 2.1 (Discrete projections and a discrepancy bound). Let be integers satisfying . There exist distinct vectors and a nonempty finite set with the following properties:
Every has norm , and every has squared norm .
For every and , Define the level index by .
For every integer and every collection of fixed coefficient vectors ,
The vectors and the set depend only on , not on the coefficient vectors.
The proof is deferred to § 2.4. Each groups the indices according to their projection levels . Having only levels allows the construction in § 2.2 to use just centers for each . Varying allows both the grouping and the parity signs to change; the discrepancy bound guarantees a common choice that produces a large coreset error, as shown in § 2.3.
A family of query center sets
Fix a weighted subset with . We construct query center sets that will show that cannot be an -coreset once the parameters are chosen appropriately. Since the copies have equal size, some copy contains at most half its points in . Denote it by and call it the active copy; the remaining copies are inactive. We use adjustable centers for and place one fixed center at each sphere center in every inactive copy. Below, we use local coordinates for and write its points as ; all centers assigned to this copy receive the same translation as its points. In this notation, denotes the weight of the corresponding translated point in , and is zero when that point is omitted from . Thus the weight-discrepancy vectors are , indexed by .
We call the label of the offsets and their corresponding points on each sphere. For a fixed , the level of is , determined by . The points on sphere with label and level form the cell
Cells may be empty. The same grouping applies on every sphere: labels are fixed, whereas levels may change with . We will use one center for all cells with the same label and level, regardless of the sphere index . Thus the active copy needs centers rather than . Figure 1 illustrates the offsets, cells, and shared query centers.
Our family is parameterized by and a sign array . For each fixed , we want the nearest-center assignments to be independent of . For a point on sphere with label and level , its squared cost should consist of a sign-independent baseline depending only on , plus a perturbation proportional to with the same positive coefficient for all points. Let be the th projection value in (3). For each , define the local center
where is the unit vector reserved for norm adjustment. Choose
The square root is well-defined: , , and imply that its radicand satisfies
The sign component has squared norm
The remaining norms are and , the latter by Lemma 2.1. Combining these values with the sign-norm calculation gives
In particular, this norm is independent of and . We include a center for every label–level pair, even when its cells are empty. Different labels have different -components; for a fixed label, different levels have different -components because the values are distinct and . Thus the active centers are distinct.
The full center set contains these active centers and the fixed sphere centers in the inactive copies. Lemma 2.5 will ensure that . We obtain exactly distinct centers by placing the remaining centers sufficiently far from , using the same additional centers for every query. The following claim verifies the assignments and costs of the resulting center sets.
Claim 2.2 (Nearest centers and costs). For every and , the center set has the following properties:
Nearest-center assignment. For every , , and , the unique nearest center of each point is .
Pointwise costs. For every ,
where , and
Every point in an inactive copy has squared cost .
Total cost. The full dataset satisfies
Proof. Fix , so that . First,
For any candidate indices and , bilinearity and orthogonality give
Substituting these quantities and (6) into the squared-distance identity gives
Here the square completion uses the two identities
The - and -components produce the label and level penalties. The norm adjustment changes no inner product with the data, supplies the quadratic term needed to complete the square, and keeps the common cost of order .
Both penalties vanish at . If , then
A wrong level therefore incurs at least . A wrong label incurs , since . Meanwhile,
Consequently, whenever ,
Thus is the unique nearest active center. Substituting removes both penalties and yields (7). The signs will align the error contributions across pairs , while distinguishes even and odd levels. Hence the cost changes reflect the distribution of weights across levels, not merely their total mass.
For completeness, the constants in (8) follow from explicit upper and lower estimates. The lower estimate is
For the upper estimate,
The same estimates hold for any sign perturbation whose absolute value is at most , a fact used in the general- extension.
We also verify that no center from another copy can be closer. In local coordinates,
where the middle bound uses (6) and . Thus all local points and centers have norm at most . The copies can be fixed in advance with translation vectors separated by at least . The reverse triangle inequality then gives a cross-copy distance of at least , whereas the triangle inequality gives a within-copy distance of at most . This separation is uniform over and .
In an inactive copy, the squared distance from to sphere center is
Thus its own sphere center is uniquely nearest, with squared cost . Additional centers are placed far enough away to affect none of these assignments. The preceding within-copy and cross-copy comparisons prove the claimed global assignments and pointwise costs. Finally,
◻
From geometric queries to a coreset error
The preceding construction realizes sign tests as differences of clustering costs. The next proposition isolates the argument that turns these tests into a lower bound against arbitrary reweighting. It will be used both for -means and for general powers .
Proposition 2.3 (Detecting omissions with paired queries). Fix . Let be a finite dataset and let consist of distinct points. Let and be supplied by Lemma 2.1. Suppose that, for every and , a set of centers satisfies where is independent of . Suppose also that for every query. Then every nonnegatively weighted subset with admits a query in this family such that
Proof. Extend by zero outside , and set . Subtracting the two signed errors and applying Eq. (10) gives
The contributions outside cancel exactly, regardless of their weights. For fixed , choosing with the sign of makes the last sum equal to . Lemma 2.1 then yields
The maximum is outside the sum: the lemma supplies one common direction for all groups, not a separate direction for each group.
Let be the number of omitted points in group . Each omitted point has discrepancy , so . Since and ,
Here follows from , including when . Combining Eqs. (12) and (13), the maximizing queries have an error gap at least . At least one has absolute error at least half this gap. Dividing by its true cost, which is at most , proves Eq. (11). ◻
Applying the proposition to -means.
Fix a weighted subset with , and choose the active copy as above. Its sphere–label pairs form the groups in Proposition 2.3. By Eq. (7), reversing changes an active point’s squared cost by
Inactive costs agree. Thus Eq. (10) holds with . Eq. (9) bounds the true cost by . The proposition therefore supplies a query with relative error at least
In particular, this error is at least whenever
Together with the coding condition and the center budget, this forces every -coreset to contain more than points. § 2.6 chooses the integer parameters simultaneously for all fixed , including , and treats the ranges where the main construction is not feasible.
Proof of Lemma 2.1: projection levels and signs
This proof is independent of the rest of the argument. The extension in § 2.5 uses only the lemma statement.
Proof of Lemma 2.1. We first construct distinct binary words such that no four distinct words sum to zero. Sums of binary words are taken coordinatewise modulo two. Suppose have been chosen. To choose , exclude
The number of excluded words is at most
The first upper bound counts at most one excluded word per previous word or previous triple; coincident exclusions can only reduce the count. Thus a valid choice exists at every step. The first exclusion ensures distinctness. The second prevents four distinct words from summing to zero, because the last word in such a relation would be the sum of three earlier words.
Let , for and , be an orthonormal basis of , and let denote the th bit of . Define
These vectors have unit norm:
If two binary words differ at coordinate , their vectors have different coefficients on and . Hence the vectors are distinct.
Draw the signs independently and uniformly from , and set
Distinct sign arrays have distinct coordinates in the basis, so the arrays yield vectors; let be their set. Moreover,
Throughout this proof, is the uniform average over , equivalently the expectation over the independent signs. This auxiliary average is used only to establish the maximum bound. Let count the coordinates with . Then
This proves (3). The same count also gives
For the moment calculations, write . Fix a coefficient vector and define
The second moment identifies the scale ; a fourth-moment bound ensures that this scale is not due only to rare large values. It suffices to prove that for every fixed subset of size or ,
For each , let be an ordinary integer sum, counting the words in whose th bit is . The other words have bit . Hence
If , distinctness gives modulo two. If , the exclusion of four-word zero sums gives the same conclusion. Thus some coordinate has odd. At that coordinate,
because an odd power of a sign equals the sign itself and the sign is uniform. By independence,
This proves (16). For a product of one or three distinct , the total multiplicity at each coordinate is odd, so at least one of has odd multiplicity. Its expectation is zero as well. Thus the signs are unbiased and four-wise independent; the following moment calculation only needs the even cases.
Every is a sign, so . Expanding the second moment gives
In the fourth moment, multiplicity patterns and reduce to products of two distinct signs; pattern uses four distinct signs. Their expectations vanish by (16). The surviving patterns are and , and the latter has orderings. Therefore,
If , the required average bound is immediate. Otherwise , so and Lemma (?) applies:
For the vectors in the lemma, let . Applying the preceding bound separately to each coefficient vector yields
Substituting the definitions of and gives (4), with one common for every coefficient vector. ◻
Lemma (Moment interpolation). Every real-valued random variable with satisfies
Proof. The first and second absolute moments are finite because for . Factor so that Hölder’s exponents are and :
Raising both sides to the power , which preserves the inequality between nonnegative quantities, gives
Dividing by proves the claim. ◻
Extending the construction to general powers
Dataset construction.
Fix a real . Each copy uses the construction of § 2.1, but the full dataset now consists of copies rather than . Their sizes satisfy
An active point will contribute to the cost, so this choice keeps the active contribution comparable to .
Center set construction.
Fix a weighted subset with , and extend by zero to . Some copy contains at most half its points in ; call it , the active copy. Write its points in local coordinates, carrying their weights along. All active centers defined below receive the translation of this copy. For every , recall that and
The query family is indexed by and . A point is intended to use the center with label and level .
To make the opposite-query cost difference independent of the level, choose the displacement as the unique solution in to
where , as in the case. To verify existence, use the bounds in Claim 2.2: both arguments in (17) lie in throughout the allowed displacement interval. Since for and , the mean value theorem gives
The left-hand side of (17) is continuous and strictly increasing from zero, so the required solution exists uniquely. It depends only on , not on or , including when ; at , it is .
For each and , define
The radicand is at least . Orthogonality gives
independently of . The active centers are distinct by their label and level components. In each inactive copy, put the centers at the translated sphere centers . The parameter choice below ensures ; place the remaining centers sufficiently far from the data.
Cost calculation.
Fix an active point , and put . For any candidate indices and , orthogonality and give
Substituting this identity, , and the center norm into the squared-distance identity yields
The last equality completes the square, exactly as for . Both penalties vanish at . A wrong level incurs at least , since ; a wrong label incurs . In contrast, the change in the sign perturbation has absolute value at most . Hence, whenever ,
using . Thus is the unique nearest active center. The unchanged local norm bound and copy separation exclude cross-copy assignments, as in Claim 2.2; the padding centers are also too far away. Inactive points retain their own sphere center as the nearest center, at distance , and therefore have cost .
It follows that every active point has powered cost
while every inactive point has cost . Therefore
The active contribution is also at least , so the total cost is .
Applying the query proposition to general powers.
For an active point at level , the sign is either or . By Eq. (18), reversing it exchanges the two perturbed squared costs. Hence
The calibration is what makes the coefficient independent of the level and the direction. Inactive costs do not change. Thus Proposition 2.3 applies to the sphere–label groups with
where the true-cost bound is Eq. (19). Any weighted subset omitting at least half of consequently admits a query with relative error at least
In particular, the error is at least if
The power-dependent gap and cost leave the same relative-error scale as for -means. It remains to choose integer parameters that also meet the center budget.
Choosing parameters in all error regimes
We now satisfy the coding condition, the center budget, and the error threshold simultaneously. The choice below applies to every fixed real . For , its threshold is smaller than in Eq. (14), so it also completes the -means argument.
Lemma 2.5 (Integer parameters for the small-error regime). Fix a real , and put . For every integer and , define There are constants , depending only on , such that the integers have the following properties. If , then If or , then .
Proof. Write and . We first bound the effect of rounding , before choosing the coefficient of . For , the difference is positive at and increasing. Hence and . Set and . Then and
For the lower bound, if then ; otherwise . The upper bounds follow from the definition of and . Moreover,
so the coding condition holds regardless of whether are positive.
Choose
Suppose first that . Since , , and ,
The choice of also controls the error. By Eq. (23) and ,
Thus the same fixed coefficient satisfies both the budget and the prescribed error threshold.
When a rounded count is positive, for . Consequently,
The dataset size therefore satisfies
This proves Eq. (22) with .
It remains to account for zero rounded counts. Since
if then gives this ratio at most . If then , so the ratio is at most . Taking proves the remaining assertion. ◻
Completing the small-error lower bound.
When , Lemma 2.5 ensures that the construction of § 2.5 is feasible, and Proposition 2.3 together with Eq. (20) forces every -coreset to have size . Otherwise, the lemma gives , so the known lower bound [10 Theorem 11] suffices for ; for , an instance of distinct points requires all points to be retained and yields . This completes the proof of Theorem 1.2.
Completing the larger-error range.
The same query family also recovers the known larger-error lower bound. Suppose . Put
For , choose
Here and , so both rounded counts are positive. The coding condition is immediate. With ,
Thus the construction applies and every coreset has size
For , the -point instance above gives . Together with Theorem 1.2 and the known upper bounds, this completes the proof of Corollary 1.3.
References
- [1]Prabhu, M., Schwiegelshohn, C., Shyam, S., & Waingarten, E. (2027). Coresets for Capacitated Clustering via Dual Concentration. Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
- [2]Huang, L., Jiang, S. H.-C., & Vishnoi, N. K. (2019). Coresets for Clustering with Fairness Constraints. Advances in Neural Information Processing Systems, 32. https://proceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.htmlproceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.html
- [3]Bandyapadhyay, S., Fomin, F. V., & Simonov, K. (2021). On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198, 23:1–23:15. https://doi.org/10.4230/LIPIcs.ICALP.2021.23
- [4]Huang, L., Jiang, S. H.-C., Lou, J., & Wu, X. (2023). Near-optimal Coresets for Robust Clustering. The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=Nc1ZkRW8Vdeopenreview.net/forum?id=Nc1ZkRW8Vde
- [5]Cohen-Addad, V., Saulpic, D., & Schwiegelshohn, C. (2021). Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. Advances in Neural Information Processing Systems, 34, 21085–21098. https://proceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.htmlproceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.html
- [6]Huang, L., Li, J., & Wu, X. (2024). On Optimal Coreset Construction for Euclidean (k, z)-Clustering. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, 1594–1604. https://doi.org/10.1145/3618260.3649707
- [7]Bansal, N., Cohen-Addad, V., Prabhu, M., Saulpic, D., & Schwiegelshohn, C. (2024). Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds. Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 1707–1723. https://doi.org/10.1109/FOCS61266.2024.00106
- [8]Har-Peled, S., & Mazumdar, S. (2004). On Coresets for k-Means and k-Median Clustering. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 291–300.
- [9]Feldman, D., & Langberg, M. (2011). A Unified Framework for Approximating and Clustering Data. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 569–578.
- [10]Cohen-Addad, V., Larsen, K. G., Saulpic, D., & Schwiegelshohn, C. (2022). Towards Optimal Lower Bounds for $k$-Median and $k$-Means Coresets. Proceedings of the 54th Annual ACM Symposium on Theory of Computing, 1038–1051. https://doi.org/10.1145/3519935.3519946
- [11]Cohen-Addad, V., Larsen, K. G., Saulpic, D., Schwiegelshohn, C., & Sheikh-Omar, O. A. (2022). Improved Coresets for Euclidean $k$-Means. Advances in Neural Information Processing Systems, 35.
- [12]Braverman, V., Cohen-Addad, V., Jiang, S. H.-C., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M. B., & Wu, X. (2022). The Power of Uniform Sampling for Coresets. 63rd IEEE Annual Symposium on Foundations of Computer Science, 462–473. https://doi.org/10.1109/FOCS54457.2022.00051
- [13]Cohen-Addad, V., Draganov, A., Russo, M., Saulpic, D., & Schwiegelshohn, C. (2025). A Tight VC-Dimension Analysis of Clustering Coresets with Applications. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 4783–4808. https://doi.org/10.1137/1.9781611978322.162
- [14]Huang, L., Jiang, Z., Li, Y., & Wu, X. (2026). Towards Tight Robust Coresets for $k$-Medians Clustering. 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), 374, 112:1–112:21. https://doi.org/10.4230/LIPIcs.ICALP.2026.112
- [15]Huang, L., Li, J., Lu, P., & Wu, X. (2025). Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 4732–4782. https://doi.org/10.1137/1.9781611978322.161
- [16]Jiang, S. H.-C., & Lou, J. (2025). Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), 334, 101:1–101:18. https://doi.org/10.4230/LIPIcs.ICALP.2025.101
- [17]Fang, Z., Huang, L., & Yang, R. (2025). Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers. Advances in Neural Information Processing Systems, 38. https://doi.org/10.52202/085713-0171
- [18]Cohen-Addad, V., Saulpic, D., & Schwiegelshohn, C. (2021). A New Coreset Framework for Clustering. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 169–182. https://doi.org/10.1145/3406325.3451022
- [19]Braverman, V., Jiang, S. H.-C., Krauthgamer, R., & Wu, X. (2021). Coresets for Clustering in Excluded-Minor Graphs and Beyond. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2679–2696. https://doi.org/10.1137/1.9781611976465.159
- [20]Feldman, D., Schmidt, M., & Sohler, C. (2020). Turning Big Data into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering. SIAM Journal on Computing, 49(3), 601–657. https://doi.org/10.1137/18M1209854
