Statement on AI Use. The perspective of using the dual for concentration, rather than the primal, was pointed out by ChatGPT-5.5 Pro. In addition, the authors used AI to help polish the writing, review the proofs, and check the manuscript for possible errors, in multiple rounds of prompting. All content was carefully examined by the authors, who take full responsibility for the content of the manuscript.
Introduction
Coresets are a staple of big data algorithms. Given a loss function, a point set P P P , and a set of candidate solutions C \mathcal{C} C , a coreset Q ⊆ P Q \subseteq P Q ⊆ P is a significantly smaller weighted set such that, for all C ∈ C C \in\mathcal{C} C ∈ C ,
cost ( Q , C ) = ( 1 ± ε ) cost ( P , C ) . \operatorname{cost}(Q,C)=(1\pm\varepsilon)\operatorname{cost}(P,C). cost ( Q , C ) = ( 1 ± ε ) cost ( P , C ) .
For a fixed accuracy parameter ε \varepsilon ε , the quality of a coreset algorithm is measured by the number of distinct points in Q Q Q , which we call its size .
In this paper, we study coresets for center-based clustering where we are typically interested in objectives of the form ∑ p ∈ P d z ( p , C ( p ) ) \sum_{p\in P}d^z(p,C(p)) ∑ p ∈ P d z ( p , C ( p )) , where d d d is the distance function of the underlying metric and C ( p ) C(p) C ( p ) is the center to which p p p is assigned from a set C C C of at most k k k centers. The most important special cases, z = 1 z=1 z = 1 and z = 2 z=2 z = 2 , are known as k k k -median and k k k -means, respectively. For the unconstrained variants, where C ( p ) = arg min c ∈ C d ( p , c ) C(p)=\arg\min_{c\in C}d(p,c) C ( p ) = arg min c ∈ C d ( p , c ) , the coreset problem is now well understood. Specifically, for finite N N N -point metrics, coresets of size O ~ ( k ε − 2 log N ) \widetilde{O}(k\varepsilon^{-2}\log N) O ( k ε − 2 log N ) are known [20 , 15 ] ; in Euclidean spaces, coresets of size O ~ ( k ε − 2 min ( k z / ( z + 2 ) , ε − z ) ) \widetilde{O}(k\varepsilon^{-2}\min(k^{z/(z+2)},\varepsilon^{-z})) O ( k ε − 2 min ( k z / ( z + 2 ) , ε − z )) are known [13 , 29 ] . These bounds are optimal up to logarithmic factors [14 , 29 ] . A more detailed review of coreset bounds for different metric spaces appears in Section A.
The situation is markedly different for constrained variants of these problems. A central example is cardinality-constrained clustering. In this paper we use the standard fractional transportation formulation: given a demand vector h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k , the objective is to minimize the k k k -median or k k k -means cost over assignments x p , i ∈ [ 0 , 1 ] x_{p,i}\in[0,1] x p , i ∈ [ 0 , 1 ] such that each point p ∈ P p\in P p ∈ P is assigned total mass ∑ i = 1 k x p , i = 1 \sum_{i=1}^{k}x_{p,i}=1 ∑ i = 1 k x p , i = 1 , and each center c i c_i c i receives total mass ∑ p ∈ P x p , i = h i \sum_{p\in P}x_{p,i}=h_i ∑ p ∈ P x p , i = h i . For unweighted point sets and integral demands, this coincides with the usual requirement that exactly h i h_i h i points are assigned to c i c_i c i .
Our coreset guarantee preserves this objective simultaneously for every choice of centers C C C and every demand vector h h h . Consequently, it also preserves the optimum over any feasible family of demand vectors. Via known reductions, see Proposition C.1 , this yields coresets for widely studied constrained clustering problems, including upper- and lower-capacitated clustering, fair clustering, and clustering with anonymity constraints.
Having established that the same coreset framework applies to these constrained variants, we next ask how large such coresets must be. More precisely, we are interested in the dependence of the coreset size on the main problem parameters, such as k k k , the accuracy parameter ε \varepsilon ε , and the dimension or metric size. This dependence is difficult to summarize succinctly. The most important barrier is that all known constructions have at least quadratic dependence on k k k [7 , 5 , 12 , 28 ] , in addition to non-optimal dependencies on other parameters. Such a quadratic dependence has historically been a major barrier even for unconstrained clustering; for cardinality-constrained clustering, it has so far proven formidable. At the same time, there is no evidence that cardinality constraints should force larger coresets than in the unconstrained setting. Thus, the guiding question of this paper is:
Do cardinality constraints fundamentally change coreset sizes for clustering?
Our Results
In this paper, we give strong evidence that the answer may be negative in general and resolve the question for finite metrics. Notably, our first main result is:
Theorem 1.1. There exists a coreset for k k k -median and k k k -means with cardinality constraints in finite N N N -point metrics of size O ( k ε − 2 log N ) O(k\varepsilon^{-2}\log N) O ( k ε − 2 log N ) .
This bound matches the best-known lower bounds for unconstrained k k k -median and k k k -means in finite metrics [14 ] , and is therefore optimal up to constant factors. Combining our finite-metric coreset with previous techniques for cardinality-constrained coreset construction already gives improved Euclidean bounds over prior work [5 , 28 ] ; see § 3 . However, this black-box route still has quadratic dependence on k k k . Our second main result breaks the quadratic barrier in k k k , with no dependence on the dimension d d d or the input size n n n .
Theorem 1.2. There exists a coreset for k k k -median (z = 1 z = 1 z = 1 ) and k k k -means (z = 2 z = 2 z = 2 ) with cardinality constraints in d d d -dimensional Euclidean spaces of size O ~ ( k ε − 2 − 2 z ) \widetilde{O}(k\varepsilon^{-2-2z}) O ( k ε − 2 − 2 z ) .
This does not match the known lower bounds for Euclidean clustering [29 ] . Nevertheless, to the best of our knowledge, it is the first cardinality-constrained coreset construction to combine near-linear dependence on k k k with competitive ε \varepsilon ε -dependence. The algorithms are efficient with the bottleneck being the computation of a constant-factor approximation.
Table 1. Coreset size bounds for cardinality-constrained clustering in d d d -dimensional Euclidean space. For each reference, the first bound is for k k k -median and the second is for k k k -means.
Preliminaries and Definitions
Notation. We use a ≲ b a \lesssim b a ≲ b to denote a ≤ η b a \leq\eta b a ≤ η b for some absolute constant η \eta η . For an integer m m m , write [ m ] = { 1 , … , m } [m] = \{1,\ldots,m\} [ m ] = { 1 , … , m } . Let Δ k = { x ∈ R k : x ≥ 0 , ∑ i x i = 1 } \Delta_k = \{x \in\mathbb{R}^k : x \geq0,\ \sum_i x_i = 1\} Δ k = { x ∈ R k : x ≥ 0 , ∑ i x i = 1 } denote the k k k -dimensional unit simplex.
The k k k -median Objective with Cardinality Constraints. Let ( X , d ) (X,d) ( X , d ) be a metric space. We first define the objective for a generic weighted instance S ⊆ X S \subseteq X S ⊆ X of total weight n n n . We write w S ( s ) w_S(s) w S ( s ) for the weight of s ∈ S s \in S s ∈ S and n = ∑ s ∈ S w S ( s ) n = \sum_{s \in S} w_S(s) n = ∑ s ∈ S w S ( s ) to denote the total weight of the instance.
Fix an ordered center tuple C = ( c 1 , … , c k ) ∈ X k C = (c_1,\ldots,c_k) \in X^k C = ( c 1 , … , c k ) ∈ X k and a demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k . The coordinate h i h_i h i is the demand of center c i c_i c i . For this demand vector h h h , the cardinality-constrained assignment cost, denoted by cost S ( C , h ) \operatorname{cost}_S(C,h) cost S ( C , h ) , is the cost of the cheapest fractional assignment of points in S S S to the centers in C C C that respects the demands h h h . Formally, it is the value of the following LP.
Table 1 (PDF p. 4).
The dual of the above LP, written alongside, will be important in the analysis later in the paper. The key reason for this is that it can be expressed succinctly. In particular, we can eliminate the auxiliary variables α s \alpha_s α s . For a fixed β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , the optimal choice of α s \alpha_s α s is
f C , β ( s ) = min i ∈ [ k ] { d ( s , c i ) + β i } . f_{C,\beta}(s)=\min_{i\in[k]}\{d(s,c_i)+\beta_i\}. f C , β ( s ) = i ∈ [ k ] min { d ( s , c i ) + β i } .
Thus the reduced dual objective is
Dual S ( C , h , β ) = ∑ s ∈ S w S ( s ) f C , β ( s ) − h ⋅ β . (1) \operatorname{Dual}_S(C,h,\beta)=\sum_{s\in S}w_S(s)f_{C,\beta}(s)-h\cdot\beta. \tag*{(1)} Dual S ( C , h , β ) = s ∈ S ∑ w S ( s ) f C , β ( s ) − h ⋅ β . (1)
We now note the following consequence of strong duality.
Claim 2.1 (Strong duality). For every weighted instance S ⊆ X S\subseteq X S ⊆ X of total weight n n n , every center tuple C = ( c 1 , … , c k ) ∈ X k C=(c_1,\ldots,c_k)\in X^k C = ( c 1 , … , c k ) ∈ X k , and every demand vector h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k ,
cost S ( C , h ) = sup β ∈ R k Dual S ( C , h , β ) . \operatorname{cost}_S(C,h)=\sup_{\beta\in\mathbb{R}^k}\operatorname{Dual}_S(C,h,\beta). cost S ( C , h ) = β ∈ R k sup Dual S ( C , h , β ) .
The same notation applies to k k k -means, with each assignment cost d ( s , c i ) d(s,c_i) d ( s , c i ) replaced by d ( s , c i ) 2 d(s,c_i)^2 d ( s , c i ) 2 . The two ambient metric spaces we consider are finite metric spaces, where X X X is finite and N = ∣ X ∣ N=|X| N = ∣ X ∣ , and Euclidean spaces, where X = R d X=\mathbb{R}^d X = R d and d ( s , c ) = ∥ s − c ∥ d(s,c)=\lVert s-c\rVert d ( s , c ) = ∥ s − c ∥ . Thus, in the Euclidean sections, the k k k -median and k k k -means assignment costs are ∥ s − c i ∥ \lVert s-c_i\rVert ∥ s − c i ∥ and ∥ s − c i ∥ 2 \lVert s-c_i\rVert^2 ∥ s − c i ∥ 2 , respectively.
Coresets. The input is an unweighted finite set P ⊆ X P\subseteq X P ⊆ X , and we write n = ∣ P ∣ n=|P| n = ∣ P ∣ .
Definition 2.2 (ε \varepsilon ε -coreset). For ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , a weighted set Q ⊆ X Q\subseteq X Q ⊆ X of total weight n n n is an ε \varepsilon ε -coreset for P P P if, for every center tuple C = ( c 1 , … , c k ) ∈ X k C=(c_1,\ldots,c_k)\in X^k C = ( c 1 , … , c k ) ∈ X k and every demand vector h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k ,
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ ε ⋅ cost P ( C , h ) . |\operatorname{cost}_Q(C,h)-\operatorname{cost}_P(C,h)|\le\varepsilon\cdot\operatorname{cost}_P(C,h). ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ ε ⋅ cost P ( C , h ) .
The size of Q Q Q is the number of distinct points in its support.
For convenience of exposition, we assume throughout that the input support has size at least k ε − 1 k\varepsilon^{-1} k ε − 1 . Otherwise, storing the entire input support is already within the claimed coreset size bounds. In the finite-metric setting, this assumption implies N ≥ k ε − 1 N\ge k\varepsilon^{-1} N ≥ k ε − 1 , and hence log ( N k / ε ) ≤ 2 log N \log(Nk/\varepsilon)\le2\log N log ( N k / ε ) ≤ 2 log N . Thus, in the finite-metric bounds, factors of log ( N k / ε ) \log(Nk/\varepsilon) log ( N k / ε ) are absorbed into log N \log N log N .
Technical Overview
In this section, we outline the key ideas underlying our analysis. We begin with the problem that admits the simplest analysis: capacitated k k k -median in finite metrics. Both capacitated k k k -means in finite metrics as well as the Euclidean space constructions follow the same basic outline, but require significant extensions.
Finite-Metric Capacitated k k k -median
Roughly speaking, the best coreset constructions have their technical origins in Chen’s seminal ring-sampling algorithm [10 ] , which we also use and proceeds by: (i) finding a distribution supported on the n n n input points P P P such that for any (fixed) set of candidate centers C C C , a small re-weighted sample from the distribution provides an accurate estimate for the cost of clustering P P P with C C C ; then, (ii) taking enough samples from the distribution so as to union-bound over all candidate centers C C C . The re-weighted set of samples drawn becomes the coreset.
Perhaps implicit, one conceptual core of Chen’s framework is that, for any fixed candidate set of centers C C C , the (unconstrained) clustering cost of P P P with C C C is a sum of n n n “local” quantities, where each point of P P P contributes its distance to the closest center in C C C , and estimating large sums via random sampling is, at least by now, a well-established algorithmic technique. In capacitated clustering, this decomposition of cost via n n n “local” summands breaks down.
Main Challenge of Capacitated Clustering. In capacitated clustering, the optimal clustering cost of P P P with respect to a fixed set of centers C C C is not a sum of individual costs over n n n dataset points; rather, it is the result of a linear program whose point-to-center assignments must satisfy global constraints (the capacities of each center).
This nonlocality is a central obstacle in capacitated clustering coresets [12 , 5 , 28 ] , and is already visible in the following simple example. Suppose P P P consists of two far-away clusters of n / 2 n/2 n /2 points and that C C C consists of two centers, c 1 c_1 c 1 and c 2 c_2 c 2 , one for each cluster with capacity n / 2 n/2 n /2 . If a coreset Q Q Q underrepresents one of the two clusters, then any feasible assignment for Q Q Q must send some weight across the large inter-cluster distance. Thus, a small error in the mass represented inside one cluster can create a large error in the capacitated clustering cost.
In the Euclidean setting, previous capacitated coresets handle this problem by breaking the input into rings around a reference solution. They sample points uniformly inside each ring and give the sampled points weights so that each ring has the correct total weight. This makes the sampling step easier to analyze. However, the capacity constraints are still global: a feasible assignment must send the right amount of mass to every center. Prior analyses handle this by controlling the assignment error separately inside the local pieces.
This local control is costly. Up to lower-order factors, Cohen-Addad and Li [12 ] obtained a bound with quadratic dependence on k k k and polylogarithmic dependence on n n n for k k k -median. Braverman et al. [5 ] removed the input-size dependence, but their bound has a larger k 3 k^3 k 3 -type dependence. Huang et al. [28 ] used a global sampling distribution together with the preprocessing of [5 ] , and obtained a k 2 k^2 k 2 -type bound. Still, the coreset size remains quadratic in k k k . We remove this quadratic dependence by preserving the dual of the constrained assignment problem directly.
The Product Ring Sampling Algorithm
Our algorithm for k k k -median in finite metrics also uses Chen’s ring-decomposition, and blends it with a global sampling distribution. The algorithm follows the following steps:
Compute an O ( 1 ) O(1) O ( 1 ) approximate k k k -median clustering with center set A A A .
Partition each cluster into log n \log n log n rings after which any two points in the same ring will have up to constant factors the same cost in A A A .
For a sampling budget ∣ Q ∣ |Q| ∣ Q ∣ , sample m R = ⌈ ∣ Q ∣ ⋅ cost ( R , A ) cost ( P , A ) ⌉ m_R = \left\lceil|Q| \cdot\frac{\operatorname{cost}(R,A)}{\operatorname{cost}(P,A)} \right\rceil m R = ⌈ ∣ Q ∣ ⋅ cost ( P , A ) cost ( R , A ) ⌉ points from ring R R R and weigh each sampled point q ∈ R ∩ Q q \in R \cap Q q ∈ R ∩ Q by w q = ∣ R ∣ / m R w_q = |R|/m_R w q = ∣ R ∣/ m R .
In other words, as in Chen’s algorithm, the sampling distribution is a product of uniform distributions over the O ( k log n ) O(k \log n) O ( k log n ) rings. The difference is that the sample size of a ring is chosen according to its importance, namely its contribution to cost ( P , A ) \operatorname{cost}(P,A) cost ( P , A ) . Because of the ceilings, the total number of sampled points is at most ∣ Q ∣ + O ( k log n ) |Q| + O(k \log n) ∣ Q ∣ + O ( k log n ) . Importantly, the algorithm does not require the sample from each ring to be a coreset for that ring by itself; such a ring-by-ring guarantee would reintroduce the factor-k k k overhead from [12 ] . Instead, our analysis treats the samples from all rings together, in one shot. A similar algorithm was proposed by Huang et al. [28 ] , using the more involved preprocessing of [5 ] in place of Chen’s decomposition.
Assignment Cost Preservation via Dual Concentration
Consider the dual program given in Equation (1) . First note that E [ Dual Q ( C , h , β ) ] = Dual P ( C , h , β ) \mathbb{E}[\operatorname{Dual}_{Q}(C,h,\beta)] = \operatorname{Dual}_{P}(C,h,\beta) E [ Dual Q ( C , h , β )] = Dual P ( C , h , β ) . Thus, if we show that the value of every dual solution β \beta β concentrates around its expectation, then strong duality implies that cost Q ( C , h ) \operatorname{cost}_{Q}(C,h) cost Q ( C , h ) concentrates around cost P ( C , h ) \operatorname{cost}_{P}(C,h) cost P ( C , h ) .
At a high level, for a fixed solution C C C and a reference solution A = { a 1 , … , a k } A = \{a_1,\ldots,a_k\} A = { a 1 , … , a k } , we replace the pointwise dual contribution f C , β ( p ) = min i ∈ [ k ] { cost ( p , c i ) + β i } f_{C,\beta}(p) = \min_{i \in[k]}\{\operatorname{cost}(p,c_i) + \beta_i\} f C , β ( p ) = min i ∈ [ k ] { cost ( p , c i ) + β i } by its anchored version g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) g_{C,\beta}(p) = f_{C,\beta}(p) - f_{C,\beta}(a_j) g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) for p ∈ P j p \in P_j p ∈ P j . The anchor contribution is preserved exactly by weight preservation within each region P j P_j P j , so concentration is only needed for the lower-variance anchored terms.
Therefore, it suffices to prove concentration for ∑ q ∈ Q w q g C , β ( q ) \sum_{q \in Q} w_q g_{C,\beta}(q) ∑ q ∈ Q w q g C , β ( q ) . The main benefit of anchoring is that ∣ g C , β ( q ) ∣ ≤ d ( q , A ) |g_{C,\beta}(q)| \le d(q,A) ∣ g C , β ( q ) ∣ ≤ d ( q , A ) . This can be thought of a dual analogue to the variance reduction trick, initially introduced by [15 ] and subsequently used in most coreset analyses. Since we can tolerate an error of the order ε ∑ p ∈ P d ( p , A ) \varepsilon\sum_{p \in P} d(p,A) ε ∑ p ∈ P d ( p , A ) , the anchoring technique effectively reduces the variance to a constant. Therefore, the modified anchored dual is preserved for any candidate β \beta β by setting ∣ Q ∣ ≳ ε − 2 |Q| \gtrsim\varepsilon^{-2} ∣ Q ∣ ≳ ε − 2 . What remains to be shown is that we can efficiently enumerate over the function space of anchored dual solutions, which, while non-trivial, is completely dominated by N k N^k N k candidate solutions. Thus, setting ∣ Q ∣ ≳ ε − 2 k log N |Q| \gtrsim\varepsilon^{-2} k \log N ∣ Q ∣ ≳ ε − 2 k log N yields a coreset for capacitated k k k -median.
Capacitated k k k -means in Finite Metrics
For the k k k -means objective, we initially follow the same outline as k k k -median, that is, the algorithm is, save for the differences in computing an initial solution, identical. The biggest difference is that the k k k -means objective requires significantly more effort to use the anchoring technique. To highlight the difference, notice that g C , β ( p ) = min i ∈ [ k ] { cost ( p , c i ) + β i } − min i ∈ [ k ] { cost ( a j , c i ) + β i } g_{C,\beta}(p) = \min_{i \in[k]}\{\operatorname{cost}(p,c_i) + \beta_i\} - \min_{i \in[k]}\{\operatorname{cost}(a_j,c_i) + \beta_i\} g C , β ( p ) = min i ∈ [ k ] { cost ( p , c i ) + β i } − min i ∈ [ k ] { cost ( a j , c i ) + β i } for any p p p assigned to a j a_j a j . Setting aside the β i \beta_i β i values, we have ∣ d 2 ( p , c i ) − d 2 ( a j , c i ) ∣ ≤ d ( p , a j ) ( d ( p , c i ) + d ( a j , c i ) ) |d^2(p,c_i) - d^2(a_j,c_i)| \le d(p,a_j)(d(p,c_i) + d(a_j,c_i)) ∣ d 2 ( p , c i ) − d 2 ( a j , c i ) ∣ ≤ d ( p , a j ) ( d ( p , c i ) + d ( a j , c i )) , which is in general not of the order cost ( p , a j ) \operatorname{cost}(p,a_j) cost ( p , a j ) . Indeed, without further modifications, it is difficult to provide any concentration. We overcome this issue in two steps. First, we truncate the solution space, showing that we can reduce to the case d ( p , c i ) ≤ ε − 1 d ( p , a j ) d(p,c_i) \le\varepsilon^{-1}d(p,a_j) d ( p , c i ) ≤ ε − 1 d ( p , a j ) . Second, we show that a weak concentration applying only to dual solutions that are near-optimal is sufficient and that achieving this weak concentration only requires ε − 2 k log N \varepsilon^{-2}k\log N ε − 2 k log N many samples.
Solution Truncation. A commonly seen argument in coreset analyses for unconstrained clustering is that if one point p p p of a ring is served at distance ε − 1 d ( p , a j ) \varepsilon^{-1}d(p,a_j) ε − 1 d ( p , a j ) , then all points in the same ring must be served at similar distance, and in fact, have nearly indistinguishable cost. While this exact property does not hold for capacitated clustering, one can nevertheless mimic features of this argument. Suppose that for some given solution C C C and demand vector h h h , some fraction f ⋅ ∣ R ∣ f\cdot|R| f ⋅ ∣ R ∣ of points from a ring R R R will be served at distance at least ε − 1 d ( p , a j ) \varepsilon^{-1}d(p,a_j) ε − 1 d ( p , a j ) . In this case, we can consider the modified instance assigning the center a j a_j a j instead of p p p , as the difference in cost is negligible. For the points where the distance depends on p p p , we thereafter have g C , β ( p ) ≤ ε − 1 cost ( p , a j ) g_{C,\beta}(p) \le\varepsilon^{-1}\operatorname{cost}(p,a_j) g C , β ( p ) ≤ ε − 1 cost ( p , a j ) . Using Hoeffding’s inequality shows that ∣ Q ∣ ≥ ε − 4 |Q| \ge\varepsilon^{-4} ∣ Q ∣ ≥ ε − 4 is sufficient to prove concentration for any fixed β \beta β . Thus, a reduction to truncated solutions already yields a coreset for ∣ Q ∣ ≳ k ε − 4 log n |Q| \gtrsim k\varepsilon^{-4}\log n ∣ Q ∣ ≳ k ε − 4 log n .
Weak Dual Convergence. For k k k -median, we simply preserved the cost of all dual solutions β \beta β up to an additive error of ε ⋅ ∑ p d ( p , A ) \varepsilon\cdot\sum_p d(p,A) ε ⋅ ∑ p d ( p , A ) . This turns out to be overkill. In order to conclude that the primal assignment cost is preserved under the coreset, we require only (i) that the cost of every near-optimal feasible dual solution β \beta β is preserved and (ii) that the cost of β \beta β that are far from optimal are not significantly overestimated. Similar ideas are sometimes used in the analysis of weak coresets, where preserving the cost of near-optimal solutions (provably) requires fewer samples than preserving the cost of all solutions [PSS26a].
For a given set of centers C C C and demand vector h h h , let β ∗ \beta^* β ∗ be an optimal dual solution on P P P , and consider any other dual solution β \beta β . If, for a sufficiently small absolute constant η \eta η , the estimation error for Dual Q ( C , h , β ) \operatorname{Dual}_Q(C,h,\beta) Dual Q ( C , h , β ) is at most η ( Dual P ( C , h , β ∗ ) − Dual P ( C , h , β ) ) \eta\left(\operatorname{Dual}_P(C,h,\beta^*)-\operatorname{Dual}_P(C,h,\beta)\right) η ( Dual P ( C , h , β ∗ ) − Dual P ( C , h , β ) ) , then β \beta β cannot attain a larger dual value than β ∗ \beta^* β ∗ on Q Q Q . In other words, the larger the gap between the dual cost of β ∗ \beta^* β ∗ and β \beta β is, the coarser we can afford to be in our estimation of Dual Q ( C , h , β ) \operatorname{Dual}_Q(C,h,\beta) Dual Q ( C , h , β ) .
Euclidean Spaces
A natural first attempt is to use the product-ring-sampling algorithm in Euclidean space. The characterization of the solution space of candidate centers and dual vectors does not pose a significant bottleneck, with essentially a union bound over exp ( O ~ ( k d ) ) \exp(\widetilde{O}(kd)) exp ( O ( k d )) solutions being sufficient. Following a suitable dimension reduction, this may be further improved to exp ( O ~ ( k ε − 2 ) ) \exp(\widetilde{O}(k\varepsilon^{-2})) exp ( O ( k ε − 2 )) many solutions. The problem with this approach is that we are guaranteed to sample at least one point from every ring, thus the overall coreset will have size O ~ ( k log n + k ε − 4 ) \widetilde{O}(k\log n+k\varepsilon^{-4}) O ( k log n + k ε − 4 ) for both k k k -median and k k k -means. Using the ring-compression ideas from [5 ] (see Theorem 3.2 of that reference), we can obtain a coreset of size O ~ ( k 2 ε − z + k ε − 4 ) \widetilde{O}(k^2\varepsilon^{-z}+k\varepsilon^{-4}) O ( k 2 ε − z + k ε − 4 ) in an almost black-box manner, where z = 1 z=1 z = 1 for k k k -median and z = 2 z=2 z = 2 for k k k -means.1 Combining these algorithms will not avoid either the k log n k\log n k log n or k 2 ε − z k^2\varepsilon^{-z} k 2 ε − z terms, so to improve further, we require a new algorithm.
Mass-Preserving Sensitivity Sampling. Sensitivity sampling [20 , 6 ] , which samples points according to their importance, is arguably the most widely used algorithmic framework in coreset construction. A popular implementation first computes a constant factor approximate solution A A A of P P P with P j P_j P j denoting the cluster induced by center a j a_j a j . Next, each point p p p is sampled with probability proportional to cost ( p , A ) cost ( P , A ) + 1 ∣ P j ∣ \frac{\operatorname{cost}(p,A)}{\operatorname{cost}(P,A)}+\frac{1}{|P_j|} cost ( P , A ) cost ( p , A ) + ∣ P j ∣ 1 and weighted appropriately. Notably, sensitivity sampling bypasses any need for ring construction, thus avoiding the overhead in coreset size arising from the number of rings.
However, standard sensitivity sampling does not preserve mass exactly, which is necessary for capacitated coresets. Previous works therefore relied on uniform sampling, a natural choice when exact mass preservation is required. Our approach instead starts with sensitivity sampling and then performs a cluster-wise weight correction. Let P j P_j P j be the reference cluster induced by anchor a j a_j a j , and let Q j Q_j Q j be the multiset of samples drawn from P j P_j P j . Each sampled occurrence q ∈ Q j q\in Q_j q ∈ Q j first receives its usual inverse-probability weight w ~ q \widetilde{w}_q w q . We then multiply all weights inside Q j Q_j Q j by the same factor λ j = ∣ P j ∣ / ∑ q ∈ Q j w ~ q \lambda_j=|P_j|/\sum_{q\in Q_j}\widetilde{w}_q λ j = ∣ P j ∣/ ∑ q ∈ Q j w q , and set w q = λ j w ~ q w_q=\lambda_j\widetilde{w}_q w q = λ j w q . Thus the final weights satisfy ∑ q ∈ Q j w q = ∣ P j ∣ \sum_{q\in Q_j}w_q=|P_j| ∑ q ∈ Q j w q = ∣ P j ∣ exactly for every reference cluster P j P_j P j . This lets us retain the advantages of sensitivity-based sampling while restoring the mass preservation needed in the capacitated setting.
Analysis. As a first observation, one might be tempted to reason that since, with very high probability w q \mathit{w}_q w q and w ~ q \widetilde{\mathit{w}}_q w q are very similar for all q q q , this modification does not significantly affect concentration properties. This intuition is incomplete. Before rescaling, the weighted sample need not preserve the cluster masses exactly. Hence capacity constraints that are feasible for P P P , and for Q Q Q with final weights w q \mathit{w}_q w q , need not be feasible for Q Q Q with initial weights w ~ q \widetilde{\mathit{w}}_q w q . Small changes in mass can therefore have a large effect on feasibility, and consequently on cost.
The dual viewpoint is again useful here. Given centers C C C and a load vector h h h , our goal is to control the dual sampling error uniformly over all dual vectors β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . Following the analysis of the product ring sampling algorithm, we first use the fact that the term − h ⋅ β -h \cdot\beta − h ⋅ β cancels when comparing Dual Q ( C , h , β ) \operatorname{Dual}_Q(C,h,\beta) Dual Q ( C , h , β ) and Dual P ( C , h , β ) \operatorname{Dual}_P(C,h,\beta) Dual P ( C , h , β ) . We then apply the anchoring trick and reduce the analysis of ∑ q ∈ Q w q g C , β ( q ) \sum_{q\in Q} \mathit{w}_q g_{C,\beta}(q) ∑ q ∈ Q w q g C , β ( q ) to two estimates. We do this by showing that, for all β \beta β ,
∣ ∑ q ∈ Q ( w ~ q − w q ) g C , β ( q ) ∣ ≤ ε ∑ p ∈ P d ( p , A ) (2) \left| \sum_{q\in Q} \left(\widetilde{\mathit{w}}_q-\mathit{w}_q\right)g_{C,\beta}(q) \right| \le\varepsilon\sum_{p\in P} d(p,A) \tag*{(2)} q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≤ ε p ∈ P ∑ d ( p , A ) (2)
and
∣ ∑ q ∈ Q w ~ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≤ ε ∑ p ∈ P d ( p , A ) . (3) \left| \sum_{q\in Q} \widetilde{\mathit{w}}_q g_{C,\beta}(q)-\sum_{p\in P} g_{C,\beta}(p) \right| \le\varepsilon\sum_{p\in P} d(p,A). \tag*{(3)} q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≤ ε p ∈ P ∑ d ( p , A ) . (3)
The second estimate is a raw sensitivity-sampling concentration bound; it does not use the final mass-preserving rescaling. The first estimate controls the additional error caused by rescaling, using that ∣ w q − w ~ q ∣ \left|\mathit{w}_q-\widetilde{\mathit{w}}_q\right| ∣ w q − w q ∣ is small and that ∣ g C , β ( q ) ∣ ≤ d ( q , A ) \left|g_{C,\beta}(q)\right| \le d(q,A) ∣ g C , β ( q ) ∣ ≤ d ( q , A ) .
One might ask where in this analysis we bypass the issue that some demand vectors may be feasible for Q Q Q after weight manipulation, but not for the initially weighted sample. The crucial trick is that, after weight manipulation, the anchor terms cancel: ∑ q ∈ Q j w q f C , β ( a j ) = ∑ p ∈ P j f C , β ( a j ) \sum_{q\in Q_j} \mathit{w}_q f_{C,\beta}(a_j) = \sum_{p\in P_j} f_{C,\beta}(a_j) ∑ q ∈ Q j w q f C , β ( a j ) = ∑ p ∈ P j f C , β ( a j ) . In contrast, ∑ q ∈ Q j w ~ q f C , β ( a j ) ≠ ∑ p ∈ P j f C , β ( a j ) \sum_{q\in Q_j} \widetilde{\mathit{w}}_q f_{C,\beta}(a_j) \ne\sum_{p\in P_j} f_{C,\beta}(a_j) ∑ q ∈ Q j w q f C , β ( a j ) = ∑ p ∈ P j f C , β ( a j ) in general, and the lack of anchor cancellation can lead to a large difference between the true dual cost and the estimated dual cost with initial weights w ~ \widetilde{\mathit{w}} w . In summary, in addition to reducing the variance, the anchoring trick isolates exactly where the weight manipulation affects the Euclidean analysis. However, the trick is only useful after the sample satisfies cluster-wise mass preservation. Without mass preservation, convergence for ∑ q ∈ Q w q g C , β ( q ) \sum_{q\in Q} \mathit{w}_q g_{C,\beta}(q) ∑ q ∈ Q w q g C , β ( q ) does not imply convergence for Dual Q ( C , h , β ) \operatorname{Dual}_Q(C,h,\beta) Dual Q ( C , h , β ) .
As a final remark, we observe that the analysis for k k k -median is now effectively identical to that of finite metrics, with the only difference being in the enumeration over candidate solutions in Euclidean spaces. The underlying ideas for enumeration are largely a combination of enumerating solutions for unconstrained k k k -median clustering in Euclidean spaces, combined with dual concentration for all demand vectors analogously to the finite metric case. For k k k -means, combining mass-preserving sensitivity sampling with the weak-dual-convergence argument from the finite-metric analysis appears more delicate. We believe this is the main remaining step toward the optimal O ~ ( k ε − 4 ) \widetilde{O}(k\varepsilon^{-4}) O ( k ε − 4 ) Euclidean k k k -means bound.
Finite-Metric Capacitated k k k -median
We first prove the coreset theorem for capacitated k k k -median in finite metrics.
Theorem 4.1 (Finite-metric fractional capacitated k k k -median). For every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , there is a randomized algorithm which outputs a weighted subset Q ⊆ P Q \subseteq P Q ⊆ P of size
∣ Q ∣ = O ( k log N + log ( 1 / δ ) ε 2 ) |Q| = O\left(\frac{k\log N+\log(1/\delta)}{\varepsilon^2}\right) ∣ Q ∣ = O ( ε 2 k log N + log ( 1/ δ ) )
such that, with probability at least 1 − δ 1-\delta 1 − δ , Q Q Q is an ε \varepsilon ε -coreset for finite-metric capacitated k k k -median.
We begin by giving the algorithm. As mentioned earlier, our algorithm is similar to the one proposed by [28 ] . It first computes an unconstrained reference k k k -median solution. It then partitions the points into rings around the reference centers. Finally, it samples points independently and uniformly from each ring, with the number of samples from a ring proportional to its contribution to the reference cost.
Coreset Construction. Let A = { a 1 , … , a k } ⊆ X A = \{a_1,\ldots,a_k\} \subseteq X A = { a 1 , … , a k } ⊆ X be a constant-factor approximate unconstrained k k k -median solution for P P P . The points of A A A are called anchors. Assign each point p ∈ P p \in P p ∈ P to its nearest anchor, breaking ties arbitrarily. For an anchor a j a_j a j , let P j P_j P j be its assigned cluster, and
Φ j = ∑ p ∈ P j d ( p , a j ) . \Phi_j = \sum_{p \in P_j} d(p,a_j). Φ j = p ∈ P j ∑ d ( p , a j ) .
Then ∑ j ∈ [ k ] Φ j ≲ OPT \sum_{j \in[k]} \Phi_j \lesssim\operatorname{OPT} ∑ j ∈ [ k ] Φ j ≲ OPT , where OPT \operatorname{OPT} OPT is the optimum unconstrained k k k -median cost of P P P .
We assume without loss of generality that no cluster has zero reference cost. Indeed, if Φ j = 0 \Phi_j = 0 Φ j = 0 , then all points in the cluster coincide with the anchor, so we store a single point with the appropriate weight. This represents the cluster exactly and increases the coreset size by at most k k k .
Ring Partitioning. For each anchor a j a_j a j , set λ j = Φ j ∣ P j ∣ \lambda_j = \frac{\Phi_j}{|P_j|} λ j = ∣ P j ∣ Φ j , and define the innermost ring by
R j , 0 = { p ∈ P j : d ( p , a j ) ≤ λ j } , R_{j,0} = \{p \in P_j : d(p,a_j) \le\lambda_j\}, R j , 0 = { p ∈ P j : d ( p , a j ) ≤ λ j } ,
and for t ≥ 1 t \ge1 t ≥ 1 , define
R j , t = { p ∈ P j : 2 t − 1 λ j < d ( p , a j ) ≤ 2 t λ j } . R_{j,t} = \{p \in P_j : 2^{t-1}\lambda_j < d(p,a_j) \le2^t\lambda_j\}. R j , t = { p ∈ P j : 2 t − 1 λ j < d ( p , a j ) ≤ 2 t λ j } .
Empty rings are discarded. Let R \mathcal{R} R denote the collection of all nonempty rings. We call these the sampled rings. For a sampled ring R = R j , t R = R_{j,t} R = R j , t , with anchor a j a_j a j , write
a R = a j , n R = ∣ R ∣ , ρ R = 2 t λ j . a_R = a_j,\qquad n_R = |R|,\qquad\rho_R = 2^t\lambda_j. a R = a j , n R = ∣ R ∣ , ρ R = 2 t λ j .
Thus,
d ( p , a R ) ≤ ρ R ∀ p ∈ R . d(p,a_R) \le\rho_R \qquad\forall p \in R. d ( p , a R ) ≤ ρ R ∀ p ∈ R .
The quantity n R ρ R n_R\rho_R n R ρ R is an upper bound, up to constants, on the total anchor cost scale of ring R R R . We use these quantities as the sampling priorities of the rings. We normalize these scales by setting
W 1 = ∑ R ∈ R n R ρ R . W_1 = \sum_{R \in\mathcal{R}} n_R\rho_R. W 1 = R ∈ R ∑ n R ρ R .
The algorithm will allocate samples to each ring R R R proportionally to n R ρ R / W 1 n_R\rho_R / W_1 n R ρ R / W 1 .
Each anchor contributes at most O ( log n ) O(\log n) O ( log n ) nonempty rings. Indeed, if the t t t -th ring around a j a_j a j is nonempty, then some point in the ring has cost larger than 2 t − 1 λ j 2^{t-1}\lambda_j 2 t − 1 λ j . Since the total cost of the cluster is Φ j = ∣ P j ∣ λ j \Phi_j = |P_j|\lambda_j Φ j = ∣ P j ∣ λ j , we have 2 t − 1 λ j < Φ j 2^{t-1}\lambda_j < \Phi_j 2 t − 1 λ j < Φ j , and hence t = O ( log ∣ P j ∣ ) = O ( log n ) t = O(\log|P_j|) = O(\log n) t = O ( log ∣ P j ∣ ) = O ( log n ) . Therefore ∣ R ∣ = O ( k log n ) |\mathcal{R}| = O(k\log n) ∣ R ∣ = O ( k log n ) .
Algorithm 1 Product Ring Sampling for Finite-Metric Capacitated k k k -median
Construct the ring partition.
Set
T = Θ ( k log N + log ( 1 / δ ) ϵ 2 ) . T = \Theta\left(\frac{k\log N+\log(1/\delta)}{\epsilon^2}\right). T = Θ ( ϵ 2 k log N + log ( 1/ δ ) ) .
For every ring R ∈ R R \in\mathcal{R} R ∈ R , sample
m R = ⌈ T n R ρ R W 1 ⌉ m_R=\left\lceil\frac{T n_R\rho_R}{W_1}\right\rceil m R = ⌈ W 1 T n R ρ R ⌉
points independently and uniformly from R R R , where W 1 = ∑ R ∈ R n R ρ R W_1=\sum_{R\in\mathcal{R}}n_R\rho_R W 1 = ∑ R ∈ R n R ρ R .
Give each sampled point from R R R weight n R / m R n_R/m_R n R / m R .
Output: the resulting weighted multiset Q Q Q .
The total number of sampled points is O ( T ) O(T) O ( T ) , because
∑ R ∈ R m R ≤ ∣ R ∣ + T = O ( T ) . \sum_{R\in\mathcal{R}}m_R\leq|\mathcal{R}|+T=O(T). R ∈ R ∑ m R ≤ ∣ R ∣ + T = O ( T ) .
The following claim shows that the normalization constant W 1 W_1 W 1 is controlled by the reference cost, and hence by OPT.
Claim 4.2. W 1 = ∑ R ∈ R n R ρ R ≲ O P T W_1=\sum_{R\in\mathcal{R}}n_R\rho_R\lesssim\mathrm{OPT} W 1 = ∑ R ∈ R n R ρ R ≲ OPT .
Proof. Fix an anchor a j a_j a j . The innermost ring has scale λ j \lambda_j λ j , so its contribution is at most ∣ P j ∣ λ j = Φ j |P_j|\lambda_j=\Phi_j ∣ P j ∣ λ j = Φ j . For every outer ring R ⊆ P j R\subseteq P_j R ⊆ P j , each point p ∈ R p\in R p ∈ R satisfies d ( p , a R ) > ρ R / 2 d(p,a_R)>\rho_R/2 d ( p , a R ) > ρ R /2 . Therefore n R ρ R ≤ 2 ∑ p ∈ R d ( p , a R ) n_R\rho_R\leq2\sum_{p\in R}d(p,a_R) n R ρ R ≤ 2 ∑ p ∈ R d ( p , a R ) . Summing first over the rings of P j P_j P j , and then over all anchors yields the claim.
Analysis
We now begin by recalling some of the notation introduced earlier. Fix an ordered center tuple C = ( c 1 , … , c k ) ∈ X k C=(c_1,\ldots,c_k)\in X^k C = ( c 1 , … , c k ) ∈ X k . For β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , recall
f C , β ( p ) = min i ∈ [ k ] { d ( p , c i ) + β i } . f_{C,\beta}(p)=\min_{i\in[k]}\{d(p,c_i)+\beta_i\}. f C , β ( p ) = i ∈ [ k ] min { d ( p , c i ) + β i } .
And for a demand vector h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k ,
Dual P ( C , h , β ) = ∑ p ∈ P f C , β ( p ) − h ⋅ β , Dual Q ( C , h , β ) = ∑ q ∈ Q w q f C , β ( q ) − h ⋅ β . (4) \operatorname{Dual}_{P}(C,h,\beta)=\sum_{p\in P}f_{C,\beta}(p)-h\cdot\beta,\qquad\operatorname{Dual}_{Q}(C,h,\beta)=\sum_{q\in Q}w_qf_{C,\beta}(q)-h\cdot\beta. \tag*{(4)} Dual P ( C , h , β ) = p ∈ P ∑ f C , β ( p ) − h ⋅ β , Dual Q ( C , h , β ) = q ∈ Q ∑ w q f C , β ( q ) − h ⋅ β . (4)
We will use Claim 2.1 (strong duality) throughout to pass between primal costs and the corresponding dual objectives.
For fixed C C C and β \beta β , the difference between the two dual objectives does not depend on the demand vector, because the terms − h ⋅ β -h\cdot\beta − h ⋅ β cancel. The dual sampling error is given by
Err C ( β ) = ∑ q ∈ Q w q f C , β ( q ) − ∑ p ∈ P f C , β ( p ) . (5) \operatorname{Err}_{C}(\beta)=\sum_{q\in Q}w_qf_{C,\beta}(q)-\sum_{p\in P}f_{C,\beta}(p). \tag*{(5)} Err C ( β ) = q ∈ Q ∑ w q f C , β ( q ) − p ∈ P ∑ f C , β ( p ) . (5)
Equivalently, for every h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k ,
Err C ( β ) = Dual Q ( C , h , β ) − Dual P ( C , h , β ) . \operatorname{Err}_{C}(\beta)=\operatorname{Dual}_{Q}(C,h,\beta)-\operatorname{Dual}_{P}(C,h,\beta). Err C ( β ) = Dual Q ( C , h , β ) − Dual P ( C , h , β ) .
To prove Theorem 4.1 , we use three lemmas.
First, for a fixed center tuple, it suffices to preserve the dual objective uniformly over all dual vectors.
Lemma 4.3 (Dual preservation implies load preservation). Fix C ∈ X k C \in X^k C ∈ X k . If
∣ Err C ( β ) ∣ ≤ η for every β ∈ R k , |\operatorname{Err}_C(\beta)| \le\eta\qquad\text{for every } \beta\in\mathbb{R}^k, ∣ Err C ( β ) ∣ ≤ η for every β ∈ R k , then
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η for every h ∈ n Δ k . |\operatorname{cost}_Q(C,h)-\operatorname{cost}_P(C,h)| \le\eta\qquad\text{for every } h \in n\Delta_k. ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η for every h ∈ n Δ k .
Second, for any fixed dual vector, the sampling error satisfies a standard concentration bound. After fixing C C C and β \beta β , the coreset contribution is an unbiased estimator of the corresponding contribution of P P P . The ring decomposition then provides uniform bounds on the magnitude of each summand, as well as the aggregate variance proxy needed for concentration.
Lemma 4.4 (Concentration for one dual vector). Fix C ∈ X k C \in X^k C ∈ X k and β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . If Q Q Q is produced by Algorithm 1 with the sample size parameter T T T defined therein, then
∣ Err C ( β ) ∣ ≤ ε OPT |\operatorname{Err}_C(\beta)| \le\varepsilon\operatorname{OPT} ∣ Err C ( β ) ∣ ≤ ε OPT with probability at least
1 − 2 exp { − Ω ( ε 2 T ) } . 1-2\exp\{-\Omega(\varepsilon^2T)\}. 1 − 2 exp { − Ω ( ε 2 T )} .
Third, the fixed-β \beta β concentration bound can be made uniform over all dual vectors. Although β \beta β ranges over the infinite set R k \mathbb{R}^k R k , the resulting cost vectors have finite combinatorial complexity, so the uniform guarantee reduces to a union bound over finitely many concentration events.
Lemma 4.5 (Uniform dual preservation for fixed centers). Fix C ∈ X k C \in X^k C ∈ X k . If
T ≳ k log N + log ( 1 / δ ) ε 2 , T \gtrsim\frac{k\log N+\log(1/\delta)}{\varepsilon^2}, T ≳ ε 2 k log N + log ( 1/ δ ) , then, with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≲ ε OPT for every β ∈ R k . |\operatorname{Err}_C(\beta)| \lesssim\varepsilon\operatorname{OPT} \qquad\text{for every } \beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≲ ε OPT for every β ∈ R k .
Proof of Theorem 4.1. Applying Lemma 4.5 to a fixed center tuple C ∈ X k C \in X^k C ∈ X k , with failure probability δ / N k \delta/N^k δ / N k , we obtain a high-probability event on which the dual error is small uniformly over all dual vectors β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . More precisely, for this fixed choice of C C C , the lemma gives
∣ Err C ( β ) ∣ ≲ ε OPT for all β ∈ R k . |\operatorname{Err}_C(\beta)| \lesssim\varepsilon\operatorname{OPT} \qquad\text{for all } \beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≲ ε OPT for all β ∈ R k .
There are at most N k N^k N k possible center tuples C ∈ X k C \in X^k C ∈ X k . Therefore, taking a union bound over all such tuples, we get that with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≲ ε OPT for every C ∈ X k and every β ∈ R k . |\operatorname{Err}_C(\beta)| \lesssim\varepsilon\operatorname{OPT} \qquad\text{for every } C \in X^k \text{ and every } \beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≲ ε OPT for every C ∈ X k and every β ∈ R k .
The sampling parameter required for this event is
T ≳ k log N + log ( 1 / δ ) ε 2 . T \gtrsim\frac{k\log N+\log(1/\delta)}{\varepsilon^2}. T ≳ ε 2 k log N + log ( 1/ δ ) .
Indeed, the only additional cost of making the guarantee simultaneous over all C ∈ X k C \in X^k C ∈ X k is the union bound over at most N k N^k N k choices of centers, which contributes an additive k log N k\log N k log N term.
We now condition on the above event. Since the dual error is controlled for every C ∈ X k C \in X^k C ∈ X k and every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , Lemma 4.3 implies that the corresponding assignment costs are preserved additively. Thus, for every center tuple C ∈ X k C \in X^k C ∈ X k and every demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≲ ε OPT ≲ ε cost P ( C , h ) . |\operatorname{cost}_Q(C,h)-\operatorname{cost}_P(C,h)| \lesssim\varepsilon\operatorname{OPT} \lesssim\varepsilon\operatorname{cost}_P(C,h). ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≲ ε OPT ≲ ε cost P ( C , h ) .
This gives the stated ε \varepsilon ε -coreset guarantee.
The rest of this section proves Lemma 4.3, Lemma 4.4, and Lemma 4.5.
Dual Cost Preservation: Proof of lem:finite-dual-to-primal
The following lemma shows that preserving the dual objective implies the coreset guarantee.
Lemma 4.3 (Dual preservation implies load preservation). Fix C ∈ X k C \in X^k C ∈ X k . If
∣ Err C ( β ) ∣ ≤ η for every β ∈ R k , |\operatorname{Err}_C(\beta)| \le\eta\qquad\text{for every } \beta\in\mathbb{R}^k, ∣ Err C ( β ) ∣ ≤ η for every β ∈ R k , then
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η for every h ∈ n Δ k . |\operatorname{cost}_Q(C,h)-\operatorname{cost}_P(C,h)| \le\eta\qquad\text{for every } h \in n\Delta_k. ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η for every h ∈ n Δ k .
Proof. By Claim 2.1 ,
cost P ( C , h ) = sup β ∈ R k Dual P ( C , h , β ) , cost Q ( C , h ) = sup β ∈ R k Dual Q ( C , h , β ) . \operatorname{cost}_P(C,h)=\sup_{\beta\in\mathbb{R}^k}\operatorname{Dual}_P(C,h,\beta), \qquad\operatorname{cost}_Q(C,h)=\sup_{\beta\in\mathbb{R}^k}\operatorname{Dual}_Q(C,h,\beta). cost P ( C , h ) = β ∈ R k sup Dual P ( C , h , β ) , cost Q ( C , h ) = β ∈ R k sup Dual Q ( C , h , β ) .
For every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k ,
Dual Q ( C , h , β ) − Dual P ( C , h , β ) = Err C ( β ) , \operatorname{Dual}_Q(C,h,\beta)-\operatorname{Dual}_P(C,h,\beta)=\operatorname{Err}_C(\beta), Dual Q ( C , h , β ) − Dual P ( C , h , β ) = Err C ( β ) ,
because the term − h ⋅ β -h\cdot\beta − h ⋅ β is identical in the two dual objectives. By assumption, ∣ Err C ( β ) ∣ ≤ η |\operatorname{Err}_C(\beta)|\le\eta ∣ Err C ( β ) ∣ ≤ η for every β \beta β . Therefore,
Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + η ∀ β ∈ R k . \operatorname{Dual}_Q(C,h,\beta)\le\operatorname{Dual}_P(C,h,\beta)+\eta\qquad\forall\beta\in\mathbb{R}^k. Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + η ∀ β ∈ R k .
Taking suprema over β \beta β gives
cost Q ( C , h ) ≤ cost P ( C , h ) + η . \operatorname{cost}_Q(C,h)\le\operatorname{cost}_P(C,h)+\eta. cost Q ( C , h ) ≤ cost P ( C , h ) + η .
The same argument with P P P and Q Q Q interchanged gives
cost P ( C , h ) ≤ cost Q ( C , h ) + η . \operatorname{cost}_P(C,h)\le\operatorname{cost}_Q(C,h)+\eta. cost P ( C , h ) ≤ cost Q ( C , h ) + η .
Combining the two inequalities yields
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η . |\operatorname{cost}_Q(C,h)-\operatorname{cost}_P(C,h)|\le\eta. ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η .
The important benefit when analyzing Err C ( β ) \operatorname{Err}_C(\beta) Err C ( β ) is that we no longer consider demand vectors. Once we prove a uniform bound on Err C ( β ) \operatorname{Err}_C(\beta) Err C ( β ) over all dual vectors β \beta β , the same event simultaneously preserves the optimum for every h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k and no union bound over demand vectors is needed.
Concentration for a fixed dual vector: Proof of lem:finite-kmedian-fixed-beta
Lemma 4.4 (Concentration for one dual vector). Fix C ∈ X k C\in X^k C ∈ X k and β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . If Q Q Q is produced by Algorithm 1 with the sample size parameter T T T defined therein, then
∣ Err C ( β ) ∣ ≤ ε OPT |\operatorname{Err}_C(\beta)|\le\varepsilon\operatorname{OPT} ∣ Err C ( β ) ∣ ≤ ε OPT with probability at least
1 − 2 exp { − Ω ( ε 2 T ) } . 1-2\exp\{-\Omega(\varepsilon^2T)\}. 1 − 2 exp { − Ω ( ε 2 T )} .
Proof. The function f C , β f_{C,\beta} f C , β is the minimum of 1-Lipschitz functions, so it is 1-Lipschitz. Thus, for every ring R ∈ R R \in\mathcal{R} R ∈ R and every point p ∈ R p \in R p ∈ R ,
∣ f C , β ( p ) − f C , β ( a R ) ∣ ≤ d ( p , a R ) ≤ ρ R . \left|f_{C,\beta}(p)-f_{C,\beta}(a_R)\right| \le d(p,a_R) \le\rho_R. ∣ f C , β ( p ) − f C , β ( a R ) ∣ ≤ d ( p , a R ) ≤ ρ R .
Fix a ring R R R . Let q R , 1 , … , q R , m R q_{R,1},\ldots,q_{R,m_R} q R , 1 , … , q R , m R be the independent uniform samples from R R R . Set
g R ( p ) = f C , β ( p ) − f C , β ( a R ) , g ˉ R = 1 n R ∑ p ∈ R g R ( p ) . g_R(p)=f_{C,\beta}(p)-f_{C,\beta}(a_R), \qquad\bar{g}_R=\frac{1}{n_R}\sum_{p\in R}g_R(p). g R ( p ) = f C , β ( p ) − f C , β ( a R ) , g ˉ R = n R 1 p ∈ R ∑ g R ( p ) .
The contribution of R R R to the sampling error is
∑ t = 1 m R n R m R ( g R ( q R , t ) − g ˉ R ) . \sum_{t=1}^{m_R}\frac{n_R}{m_R}\left(g_R(q_{R,t})-\bar{g}_R\right). t = 1 ∑ m R m R n R ( g R ( q R , t ) − g ˉ R ) .
The summands are independent and mean zero. Each has magnitude at most 2 n R ρ R / m R 2n_R\rho_R/m_R 2 n R ρ R / m R . Hoeffding’s inequality (see B.1) gives, for every s > 0 s>0 s > 0 ,
Pr { ∣ Err C ( β ) ∣ ≥ s } ≤ 2 exp ( − Ω ( s 2 ∑ R ∈ R ( n R ρ R ) 2 / m R ) ) . \Pr\left\{\left|\operatorname{Err}_C(\beta)\right|\ge s\right\}
\le2\exp\left(-\Omega\left(\frac{s^2}{\sum_{R\in\mathcal{R}}(n_R\rho_R)^2/m_R}\right)\right). Pr { ∣ Err C ( β ) ∣ ≥ s } ≤ 2 exp ( − Ω ( ∑ R ∈ R ( n R ρ R ) 2 / m R s 2 ) ) .
The sampling rule implies
∑ R ∈ R ( n R ρ R ) 2 m R ≤ W 1 2 T . \sum_{R\in\mathcal{R}}\frac{(n_R\rho_R)^2}{m_R}\le\frac{W_1^2}{T}. R ∈ R ∑ m R ( n R ρ R ) 2 ≤ T W 1 2 .
By Claim 4.2 , W 1 ≲ OPT W_1\lesssim\operatorname{OPT} W 1 ≲ OPT . Taking s = ε OPT s=\varepsilon\operatorname{OPT} s = ε OPT proves the lemma.
Uniform Preservation over Dual Vectors: Proof of Lemma 4.5
It remains to make the fixed-β \beta β concentration statement uniform over all dual vectors. Fix a center tuple C ∈ X k C\in X^k C ∈ X k . Our goal in this subsection is to prove that, with high probability,
∣ Err C ( β ) ∣ ≲ ε OPT for every β ∈ R k . \left|\operatorname{Err}_C(\beta)\right|\lesssim\varepsilon\operatorname{OPT}
\qquad\text{for every }\beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≲ ε OPT for every β ∈ R k .
The difficulty is that β \beta β ranges over an infinite set. We overcome this by showing that the sampling error depends on β \beta β only through a residual vector, and that the set of all such residual vectors admits a small discretization.
For a ring R R R and a point p ∈ R p\in R p ∈ R , define the normalized residual
G C , β ( R , p ) = f C , β ( p ) − f C , β ( a R ) ρ R . G_{C,\beta}(R,p)=\frac{f_{C,\beta}(p)-f_{C,\beta}(a_R)}{\rho_R}. G C , β ( R , p ) = ρ R f C , β ( p ) − f C , β ( a R ) .
Since f C , β f_{C,\beta} f C , β is 1-Lipschitz and d ( p , a R ) ≤ ρ R d(p,a_R)\le\rho_R d ( p , a R ) ≤ ρ R , we have ∣ G C , β ( R , p ) ∣ ≤ 1 \left|G_{C,\beta}(R,p)\right|\le1 ∣ G C , β ( R , p ) ∣ ≤ 1 . Thus,
G C , β ∈ [ − 1 , 1 ] D , D = { ( R , p ) : R ∈ R , p ∈ R } . G_{C,\beta}\in[-1,1]^{\mathcal{D}},\qquad
\mathcal{D}=\{(R,p):R\in\mathcal{R},\ p\in R\}. G C , β ∈ [ − 1 , 1 ] D , D = {( R , p ) : R ∈ R , p ∈ R } .
The following observation provides the deterministic link between approximation in the residual space and approximation of the dual sampling error. First, after centering at the anchor of each ring, the anchor terms cancel exactly. Indeed, the sampled total weight from R R R is exactly n R n_R n R , so the contribution of the constant value f C , β ( a R ) f_{C,\beta}(a_R) f C , β ( a R ) is the same from the sampled copy of R R R in Q Q Q and from the original ring R R R . Therefore
Err C ( β ) = ∑ R ∈ R ρ R ( n R m R ∑ t = 1 m R G C , β ( R , q R , t ) − ∑ p ∈ R G C , β ( R , p ) ) . \operatorname{Err}_{C}(\beta)=\sum_{R\in\mathcal{R}}\rho_R\left(\frac{n_R}{m_R}\sum_{t=1}^{m_R}G_{C,\beta}(R,q_{R,t})-\sum_{p\in R}G_{C,\beta}(R,p)\right). Err C ( β ) = R ∈ R ∑ ρ R m R n R t = 1 ∑ m R G C , β ( R , q R , t ) − p ∈ R ∑ G C , β ( R , p ) .
Thus Err C ( β ) \operatorname{Err}_{C}(\beta) Err C ( β ) is controlled entirely by the normalized residual vector G C , β G_{C,\beta} G C , β . Second, this dependence is Lipschitz in the ℓ ∞ \ell_\infty ℓ ∞ norm. Suppose β , β ′ ∈ R k \beta,\beta'\in\mathbb{R}^k β , β ′ ∈ R k satisfy
∥ G C , β − G C , β ′ ∥ ∞ ≤ γ . \lVert G_{C,\beta}-G_{C,\beta'}\rVert_\infty\leq\gamma. ∥ G C , β − G C , β ′ ∥ ∞ ≤ γ .
Then, for every realization of the sample,
∣ Err C ( β ) − Err C ( β ′ ) ∣ ≤ ∑ R ∈ R ρ R ( n R m R ∑ t = 1 m R γ + ∑ p ∈ R γ ) = 2 γ ∑ R ∈ R n R ρ R = 2 γ W 1 . (6) \begin{aligned}
\left|\operatorname{Err}_{C}(\beta)-\operatorname{Err}_{C}(\beta')\right|\leq\sum_{R\in\mathcal{R}}\rho_R\left(\frac{n_R}{m_R}\sum_{t=1}^{m_R}\gamma+\sum_{p\in R}\gamma\right) \\
&=2\gamma\sum_{R\in\mathcal{R}}n_R\rho_R=2\gamma W_1. \tag*{(6)}
\end{aligned} ∣ Err C ( β ) − Err C ( β ′ ) ∣ ≤ R ∈ R ∑ ρ R m R n R t = 1 ∑ m R γ + p ∈ R ∑ γ = 2 γ R ∈ R ∑ n R ρ R = 2 γ W 1 . (6)
Consequently, if every G C , β G_{C,\beta} G C , β is within γ \gamma γ in ℓ ∞ \ell_\infty ℓ ∞ distance of some representative G C , β ^ G_{C,\widehat{\beta}} G C , β , then concentration for the representatives extends to all dual vectors with an additional loss of at most 2 γ W 1 2\gamma W_1 2 γ W 1 . Since W 1 ≤ OPT W_1\leq\operatorname{OPT} W 1 ≤ OPT , choosing γ \gamma γ to be a sufficiently small constant multiple of ε \varepsilon ε makes this loss O ( ε ) OPT O(\varepsilon)\operatorname{OPT} O ( ε ) OPT . It remains to show that the residual vectors induced by dual solutions admit a small such net.
Lemma 4.6 (Net for residual vectors). For every γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) , there is a set B C ( γ ) ⊆ R k \mathcal{B}_C(\gamma)\subseteq\mathbb{R}^k B C ( γ ) ⊆ R k with
∣ B C ( γ ) ∣ ≤ ( N k γ ) O ( k ) \lvert\mathcal{B}_C(\gamma)\rvert\leq\left(\frac{Nk}{\gamma}\right)^{O(k)} ∣ B C ( γ )∣ ≤ ( γ N k ) O ( k ) such that for every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , there exists β ^ ∈ B C ( γ ) \widehat{\beta}\in\mathcal{B}_C(\gamma) β ∈ B C ( γ ) satisfying
∥ G C , β − G C , β ^ ∥ ∞ ≤ γ . \lVert G_{C,\beta}-G_{C,\widehat{\beta}}\rVert_\infty\leq\gamma. ∥ G C , β − G C , β ∥ ∞ ≤ γ .
Proof. We first bound the number of possible minimizer patterns. Since every input point and every anchor lie in X X X , it suffices to consider the values of f C , β f_{C,\beta} f C , β on points of X X X . For every z ∈ X z\in X z ∈ X and every pair i , j ∈ [ k ] i,j\in[k] i , j ∈ [ k ] , consider the hyperplane
d ( z , c i ) + β i = d ( z , c j ) + β j d(z,c_i)+\beta_i=d(z,c_j)+\beta_j d ( z , c i ) + β i = d ( z , c j ) + β j
in R k \mathbb{R}^k R k . There are M = O ( N k 2 ) M=O(Nk^2) M = O ( N k 2 ) such hyperplanes. The induced arrangement decomposes R k \mathbb{R}^k R k into faces on which all comparisons
d ( z , c i ) + β i versus d ( z , c j ) + β j d(z,c_i)+\beta_i\quad\text{versus}\quad d(z,c_j)+\beta_j d ( z , c i ) + β i versus d ( z , c j ) + β j
are fixed, allowing equality. After applying a fixed tie-breaking rule, each face therefore determines a single minimizer pattern
π β ( z ) ∈ arg min i ∈ [ k ] { d ( z , c i ) + β i } , z ∈ X . \pi_\beta(z)\in\underset{i\in[k]}{\arg\min}\{d(z,c_i)+\beta_i\},\qquad z\in X. π β ( z ) ∈ i ∈ [ k ] arg min { d ( z , c i ) + β i } , z ∈ X .
The number of faces in an arrangement of M M M hyperplanes in R k \mathbb{R}^k R k is M O ( k ) M^{O(k)} M O ( k ) . Hence the number of possible minimizer patterns is at most
( O ( N k 2 ) ) O ( k ) = exp { O ( k log ( N k ) ) } . \left(O(Nk^2)\right)^{O(k)}=\exp\{O(k\log(Nk))\}. ( O ( N k 2 ) ) O ( k ) = exp { O ( k log ( N k ))} .
Fix one such pattern π \pi π . For every β \beta β inducing π \pi π ,
f C , β ( z ) = d ( z , c π ( z ) ) + β π ( z ) ∀ z ∈ X . f_{C,\beta}(z)=d(z,c_{\pi(z)})+\beta_{\pi(z)} \qquad\forall z\in X. f C , β ( z ) = d ( z , c π ( z ) ) + β π ( z ) ∀ z ∈ X .
Thus, for every ( R , p ) ∈ D (R,p)\in\mathcal{D} ( R , p ) ∈ D ,
G C , β ( R , p ) = d ( p , c π ( p ) ) − d ( a R , c π ( a R ) ) + β π ( p ) − β π ( a R ) ρ R . G_{C,\beta}(R,p)=\frac{d(p,c_{\pi(p)})-d(a_R,c_{\pi(a_R)})+\beta_{\pi(p)}-\beta_{\pi(a_R)}}{\rho_R}. G C , β ( R , p ) = ρ R d ( p , c π ( p ) ) − d ( a R , c π ( a R ) ) + β π ( p ) − β π ( a R ) .
Therefore, once π \pi π is fixed, the residual vector G C , β G_{C,\beta} G C , β is an affine function of β \beta β . The set of residual vectors inducing this pattern lies in an affine subspace of dimension at most k k k , equipped with the norm inherited from ℓ ∞ ( D ) \ell_\infty(\mathcal{D}) ℓ ∞ ( D ) , and also lies in the cube [ − 1 , 1 ] D [-1,1]^{\mathcal{D}} [ − 1 , 1 ] D .
By the standard volumetric covering argument [42 Proposition 4.2.10] , applied inside the k k k -dimensional affine hull with the induced ℓ ∞ \ell_\infty ℓ ∞ norm, any subset of a k k k -dimensional affine subspace with ℓ ∞ \ell_\infty ℓ ∞ -diameter at most 2 2 2 has a γ \gamma γ -net of size at most
( C 0 γ ) k . \left(\frac{C_0}{\gamma}\right)^k. ( γ C 0 ) k .
where C 0 > 0 C_0>0 C 0 > 0 is a universal constant. Applying this bound to the residual vectors inducing the fixed pattern gives such a net. Moreover, by taking a maximal γ \gamma γ -separated subset of the induced residual vectors, the net points may be chosen to be induced by actual dual vectors.
Taking the union over all minimizer patterns gives a net of size at most
exp { O ( k log ( N k ) ) } ⋅ ( C 0 γ ) k ≤ ( N k γ ) O ( k ) . \exp\{O(k\log(Nk))\}\cdot\left(\frac{C_0}{\gamma}\right)^k
\leq\left(\frac{Nk}{\gamma}\right)^{O(k)}. exp { O ( k log ( N k ))} ⋅ ( γ C 0 ) k ≤ ( γ N k ) O ( k ) .
Choosing one dual vector representative for each net point gives B C ( γ ) \mathcal{B}_C(\gamma) B C ( γ ) .
We now use the residual net to generalize the fixed-β \beta β concentration bound to a statement that holds simultaneously for every dual vector.
Lemma 4.5 (Uniform dual preservation for fixed centers). Fix C ∈ X k C\in X^k C ∈ X k . If
T ≳ k log N + log ( 1 / δ ) ε 2 , T\gtrsim\frac{k\log N+\log(1/\delta)}{\varepsilon^2}, T ≳ ε 2 k log N + log ( 1/ δ ) , then, with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≲ ε O P T for every β ∈ R k . |\operatorname{Err}_C(\beta)|\lesssim\varepsilon\mathrm{OPT}
\qquad\text{for every }\beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≲ ε OPT for every β ∈ R k . Proof. Let γ = c 0 ε \gamma=c_0\varepsilon γ = c 0 ε , where c 0 c_0 c 0 is a sufficiently small constant. Apply Lemma 4.4 to every β ^ ∈ B C ( γ ) \widehat{\beta}\in\mathcal{B}_C(\gamma) β ∈ B C ( γ ) , and take a union bound using Lemma 4.6. With probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ^ ) ∣ ≤ 1 2 ε O P T for every β ^ ∈ B C ( γ ) , |\operatorname{Err}_C(\widehat{\beta})|\leq\frac{1}{2}\varepsilon\mathrm{OPT}
\qquad\text{for every }\widehat{\beta}\in\mathcal{B}_C(\gamma), ∣ Err C ( β ) ∣ ≤ 2 1 ε OPT for every β ∈ B C ( γ ) ,
provided that
T ≳ k log N + log ( 1 / δ ) ε 2 . T \gtrsim\frac{k\log N+\log(1/\delta)}{\varepsilon^2}. T ≳ ε 2 k log N + log ( 1/ δ ) .
Now fix an arbitrary β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , and choose β ^ ∈ B C ( γ ) \hat{\beta} \in\mathcal{B}_C(\gamma) β ^ ∈ B C ( γ ) with
∥ G C , β − G C , β ^ ∥ ∞ ≤ γ . \lVert G_{C,\beta}-G_{C,\hat{\beta}}\rVert_{\infty}\leq\gamma. ∥ G C , β − G C , β ^ ∥ ∞ ≤ γ .
By (6) , we have
∣ Err C ( β ) − Err C ( β ^ ) ∣ ≤ 2 γ W 1 . \lvert\operatorname{Err}_C(\beta)-\operatorname{Err}_C(\hat{\beta})\rvert\leq2\gamma W_1. ∣ Err C ( β ) − Err C ( β ^ )∣ ≤ 2 γ W 1 .
Using W 1 ≲ O P T W_1\lesssim\mathrm{OPT} W 1 ≲ OPT , and choosing c 0 c_0 c 0 sufficiently small, this is at most ε O P T / 2 \varepsilon\mathrm{OPT}/2 ε OPT /2 . Therefore,
∣ Err C ( β ) ∣ ≤ ∣ Err C ( β ^ ) ∣ + ∣ Err C ( β ) − Err C ( β ^ ) ∣ ≤ ε O P T . \lvert\operatorname{Err}_C(\beta)\rvert\leq\lvert\operatorname{Err}_C(\hat{\beta})\rvert+\lvert\operatorname{Err}_C(\beta)-\operatorname{Err}_C(\hat{\beta})\rvert\leq\varepsilon\mathrm{OPT}. ∣ Err C ( β )∣ ≤ ∣ Err C ( β ^ )∣ + ∣ Err C ( β ) − Err C ( β ^ )∣ ≤ ε OPT .
Since β \beta β was arbitrary, the bound holds uniformly over R k \mathbb{R}^k R k .
Finite-Metric Capacitated k k k -means
We next prove the coreset theorem for capacitated k k k -means in finite metrics.
Theorem 5.1 (Finite-metric fractional capacitated k k k -means). For every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , there is a randomized algorithm which outputs a weighted subset Q ⊆ P Q\subseteq P Q ⊆ P of size
∣ Q ∣ = O ( k log N + log ( 1 / δ ) ε 2 ) . \lvert Q\rvert=O\left(\frac{k\log N+\log(1/\delta)}{\varepsilon^2}\right). ∣ Q ∣ = O ( ε 2 k log N + log ( 1/ δ ) ) . such that, with probability at least 1 − δ 1-\delta 1 − δ , Q Q Q is an ε \varepsilon ε -coreset for finite-metric capacitated k k k -means.
Coreset Construction. The construction is the same as in the k k k -median section, with squared distances replacing distances.
Let A = { a 1 , … , a k } A=\{a_1,\ldots,a_k\} A = { a 1 , … , a k } be a constant-factor approximate unconstrained k k k -means solution for P P P . The points of A A A are called anchors. Assign each point p ∈ P p\in P p ∈ P to its nearest anchor, breaking ties arbitrarily. For an anchor a j a_j a j , let P j P_j P j be its assigned cluster, and set Φ j = ∑ p ∈ P j d ( p , a j ) 2 \Phi_j=\sum_{p\in P_j}d(p,a_j)^2 Φ j = ∑ p ∈ P j d ( p , a j ) 2 . Then ∑ j ∈ [ k ] Φ j ≲ O P T \sum_{j\in[k]}\Phi_j\lesssim\mathrm{OPT} ∑ j ∈ [ k ] Φ j ≲ OPT , where O P T \mathrm{OPT} OPT is the optimum unconstrained k k k -means cost of P P P .
We assume without loss of generality that no cluster has zero reference cost. Indeed, if Φ j = 0 \Phi_j=0 Φ j = 0 , then all points in the cluster coincide with the anchor, so we store a single point with the appropriate weight. This represents the cluster exactly and increases the coreset size by at most k k k .
Ring Partitioning. For each anchor a j a_j a j , set λ j = Φ j ∣ P j ∣ \lambda_j=\frac{\Phi_j}{\lvert P_j\rvert} λ j = ∣ P j ∣ Φ j . We partition P j P_j P j by squared distance from its anchor. Define the innermost ring by
R j , 0 = { p ∈ P j : d ( p , a j ) 2 ≤ λ j } , R_{j,0}=\{p\in P_j:d(p,a_j)^2\leq\lambda_j\}, R j , 0 = { p ∈ P j : d ( p , a j ) 2 ≤ λ j } ,
and for t ≥ 1 t\geq1 t ≥ 1 , define
R j , t = { p ∈ P j : 2 t − 1 λ j < d ( p , a j ) 2 ≤ 2 t λ j } . R_{j,t}=\{p\in P_j:2^{t-1}\lambda_j<d(p,a_j)^2\leq2^t\lambda_j\}. R j , t = { p ∈ P j : 2 t − 1 λ j < d ( p , a j ) 2 ≤ 2 t λ j } .
Empty rings are discarded.
Let R \mathcal{R} R denote the collection of all nonempty rings. We call these the sampled rings. For a sampled ring R = R j , t R=R_{j,t} R = R j , t , write
a R = a j , n R = ∣ R ∣ , ρ R 2 = 2 t λ j . a_R=a_j,\qquad n_R=\lvert R\rvert,\qquad\rho_R^2=2^t\lambda_j. a R = a j , n R = ∣ R ∣ , ρ R 2 = 2 t λ j .
Thus,
d ( p , a R ) 2 ≤ ρ R 2 ∀ p ∈ R . d(p,a_R)^2 \le\rho_R^2 \qquad\forall p \in R. d ( p , a R ) 2 ≤ ρ R 2 ∀ p ∈ R .
The quantity n R ρ R 2 n_R\rho_R^2 n R ρ R 2 is an upper bound, up to constants, on the total anchor cost scale of ring R R R . We use these quantities as the sampling priorities of the rings. We normalize these scales by setting
W 2 = ∑ R ∈ R n R ρ R 2 . W_2 = \sum_{R \in\mathcal{R}} n_R\rho_R^2. W 2 = R ∈ R ∑ n R ρ R 2 .
The algorithm will allocate samples to each ring R R R proportionally to n R ρ R 2 / W 2 n_R\rho_R^2/W_2 n R ρ R 2 / W 2 .
Each anchor contributes at most O ( log n ) O(\log n) O ( log n ) sampled rings. Indeed, if R j , t R_{j,t} R j , t is nonempty for some t ≥ 1 t \ge1 t ≥ 1 , then some point in the ring has squared distance larger than 2 t − 1 λ j 2^{t-1}\lambda_j 2 t − 1 λ j from a j a_j a j . Since the total squared cost of the cluster is Φ j = ∣ P j ∣ λ j \Phi_j = |P_j|\lambda_j Φ j = ∣ P j ∣ λ j , we have
2 t − 1 λ j < Φ j = ∣ P j ∣ λ j , 2^{t-1}\lambda_j < \Phi_j = |P_j|\lambda_j, 2 t − 1 λ j < Φ j = ∣ P j ∣ λ j ,
and hence t = O ( log ∣ P j ∣ ) t = O(\log|P_j|) t = O ( log ∣ P j ∣ ) . Therefore,
∣ R ∣ = O ( k log n ) . |\mathcal{R}| = O(k\log n). ∣ R ∣ = O ( k log n ) .
Sampling. For each ring R R R , sample m R = ⌈ T n R ρ R 2 / W 2 ⌉ m_R = \lceil Tn_R\rho_R^2/W_2\rceil m R = ⌈ T n R ρ R 2 / W 2 ⌉ points independently and uniformly from R R R , and give each sampled point weight n R / m R n_R/m_R n R / m R . Here T = Θ ( ( k log N + log ( 1 / δ ) ) / ε 2 ) T = \Theta((k\log N + \log(1/\delta))/\varepsilon^2) T = Θ (( k log N + log ( 1/ δ )) / ε 2 ) . The total number of points sampled in the coreset is O ( T ) O(T) O ( T ) .
Claim 5.2. The squared ring scales satisfy W 2 = ∑ R ∈ R n R ρ R 2 ≲ O P T W_2 = \sum_{R \in\mathcal{R}} n_R\rho_R^2 \lesssim\mathrm{OPT} W 2 = ∑ R ∈ R n R ρ R 2 ≲ OPT .
The proof of the above claim is identical to Claim 4.2 with squared distances replacing distances.
Analysis
The proof follows the same duality template as the k k k -median analysis, but squared distances introduce an additional difficulty. After centering at a ring anchor, the difference
d ( p , c ) 2 − d ( a R , c ) 2 d(p,c)^2 - d(a_R,c)^2 d ( p , c ) 2 − d ( a R , c ) 2
is not controlled only by the squared ring scale ρ R 2 \rho_R^2 ρ R 2 ; it also contains a cross term depending on the distance from the anchor a R a_R a R to the candidate center c c c . This prevents a direct application of Hoeffding’s inequality to ensure concentration.
First, we introduce a truncated ring-labelled objective. For centers that are far from a ring, we replace the point-center squared distance by the corresponding anchor-center squared distance. This changes every feasible assignment cost by only a 1 ± O ( ε ) 1 \pm O(\varepsilon) 1 ± O ( ε ) factor, while restoring bounded variation within a ring. This is in fact enough to show that coresets of size O ~ ( k ε − 4 ) \widetilde{O}(k\varepsilon^{-4}) O ( k ε − 4 ) suffice.
Second, we use a weak dual convergence argument. Unlike in the k k k -median proof, we do not approximate every dual vector to the same additive accuracy. Dual vectors that are close to optimal are preserved accurately while dual vectors far from optimal may be approximated more coarsely, because their dual value is already too small to affect the maximum. This is the step that recovers the O ~ ( k ε − 2 ) \widetilde{O}(k\varepsilon^{-2}) O ( k ε − 2 ) sample dependence.
We now make these two ingredients formal. The proof is organized around three lemmas. First, we define the truncated objective formally and show that it is a good approximation for the original k k k -means objective.
Truncation. The truncation step separates the case where a candidate center is much farther from the anchor than the scale of the ring. In this case, replacing the point-center cost by the corresponding anchor-center cost changes the cost only by a 1 ± O ( ε ) 1 \pm O(\varepsilon) 1 ± O ( ε ) factor. This restores bounded within-ring variation for the truncated objective.
Definition 5.3 (Truncated costs). For a point p p p , define the truncated cost of assigning p p p to center c i c_i c i as follows. If p p p belongs to a sampled ring R ∈ R R \in\mathcal{R} R ∈ R , set
ℓ ~ i ( p ) = { d ( p , c i ) 2 , if d ( a R , c i ) ≤ ρ R / ε , d ( a R , c i ) 2 , if d ( a R , c i ) > ρ R / ε . \widetilde{\ell}_i(p) =
\begin{cases}
d(p,c_i)^2, & \text{if } d(a_R,c_i) \le\rho_R/\varepsilon, \\
d(a_R,c_i)^2, & \text{if } d(a_R,c_i) > \rho_R/\varepsilon.
\end{cases} ℓ i ( p ) = { d ( p , c i ) 2 , d ( a R , c i ) 2 , if d ( a R , c i ) ≤ ρ R / ε , if d ( a R , c i ) > ρ R / ε . If p p p belongs to a cluster that is represented exactly, set ℓ ~ i ( p ) = d ( p , c i ) 2 \widetilde{\ell}_i(p) = d(p,c_i)^2 ℓ i ( p ) = d ( p , c i ) 2 . When evaluating the centered anchor term for a sampled ring R R R , we set ℓ ~ i ( a R ) : = d ( a R , c i ) 2 \widetilde{\ell}_i(a_R) := d(a_R,c_i)^2 ℓ i ( a R ) := d ( a R , c i ) 2 .
For a weighted instance S S S supported on P P P and a demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k , let cost ~ S ( C , h ) \widetilde{\operatorname{cost}}_S(C,h) cost S ( C , h ) denote the optimum value of the fractional assignment LP on S S S with demand vector h h h , where assigning p p p to c i c_i c i has cost ℓ ~ i ( p ) \widetilde{\ell}_i(p) ℓ i ( p ) .
Lemma 5.4 (Truncation comparison). For every weighted ring-labelled instance S S S , every center tuple C ∈ X k C \in X^k C ∈ X k , and every demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
cost ~ S ( C , h ) = ( 1 ± O ( ε ) ) cost S ( C , h ) . \widetilde{\operatorname{cost}}_S(C,h) = (1 \pm O(\varepsilon))\operatorname{cost}_S(C,h). cost S ( C , h ) = ( 1 ± O ( ε )) cost S ( C , h ) .
We next formulate the weak dual convergence condition. For the rest of the k k k -means analysis, all dual quantities are defined with respect to the truncated costs ℓ ~ i \widetilde{\ell}_i ℓ i .
Dual formulation. We use the same dual formulation as in the k k k -median section, with the original costs being replaced by the truncated costs ℓ ~ i \widetilde{\ell}_i ℓ i . Thus the truncated objective cost ~ S ( C , h ) \widetilde{\operatorname{cost}}_S(C,h) cost S ( C , h ) can be written as the supremum of a reduced dual objective over β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . As before, when comparing P P P and Q Q Q , the load term − h ⋅ β -h \cdot\beta − h ⋅ β cancels. Therefore the sampling error depends only on C C C and β \beta β , not on the demand vector h h h .
Weak dual convergence. The weak dual convergence argument uses a nonuniform notion of dual preservation. A dual vector that is nearly optimal for the instance must be preserved accurately, while a dual vector whose population dual value is far below the optimum may be preserved more coarsely.
Definition 5.5 (Dual gap and allowed error). Fix C ∈ X k C \in X^k C ∈ X k , h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k , and β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . The truncated dual gap of β \beta β with respect to C , h C,h C , h is
Δ C , h ( β ) = cost ~ P ( C , h ) − Dual P ( C , h , β ) . \Delta_{C,h}(\beta) = \widetilde{\operatorname{cost}}_P(C,h) - \operatorname{Dual}_P(C,h,\beta). Δ C , h ( β ) = cost P ( C , h ) − Dual P ( C , h , β ) . By strong duality, Δ C , h ( β ) ≥ 0 \Delta_{C,h}(\beta) \ge0 Δ C , h ( β ) ≥ 0 .
For fixed C C C and β \beta β , define the allowed error
A C ( β ) = inf h ∈ n Δ k { ε cost ~ P ( C , h ) + 1 4 Δ C , h ( β ) } . A_C(\beta) = \inf_{h \in n\Delta_k} \left\{ \varepsilon\widetilde{\operatorname{cost}}_P(C,h) + \frac{1}{4}\Delta_{C,h}(\beta) \right\}. A C ( β ) = h ∈ n Δ k inf { ε cost P ( C , h ) + 4 1 Δ C , h ( β ) } .
The next lemma explains why this is the right notion of dual control. It says that controlling the sampling error only up to the allowed error is already enough to preserve the truncated exact-load objective.
Lemma 5.6 (Allowed-error dual preservation). Fix C ∈ X k C \in X^k C ∈ X k . Suppose that
∣ Err C ( β ) ∣ ≤ A C ( β ) for every β ∈ R k . \lvert\operatorname{Err}_C(\beta) \rvert\le A_C(\beta) \qquad\text{for every } \beta\in\mathbb{R}^k. ∣ Err C ( β )∣ ≤ A C ( β ) for every β ∈ R k .
Then, for every demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
cost ~ Q ( C , h ) = ( 1 ± O ( ε ) ) cost ~ P ( C , h ) . \widetilde{\operatorname{cost}}_Q(C,h) = (1 \pm O(\varepsilon))\widetilde{\operatorname{cost}}_P(C,h). cost Q ( C , h ) = ( 1 ± O ( ε )) cost P ( C , h ) .
It remains to prove that the sampled instance satisfies the allowed-error condition. This is the main sampling statement for k k k -means. It is the step that improves the sample dependence from the naive O ~ ( k ε − 4 ) \widetilde{O}(k\varepsilon^{-4}) O ( k ε − 4 ) bound obtained from uniform Hoeffding’s inequality to the desired O ~ ( k ε − 2 ) \widetilde{O}(k\varepsilon^{-2}) O ( k ε − 2 ) bound.
Lemma 5.7 (Uniform weak dual convergence for fixed centers). Fix C ∈ X k C \in X^k C ∈ X k . If
T ≳ k log N + log ( 1 / δ ) ε 2 , T \gtrsim\frac{k \log N + \log(1/\delta)}{\varepsilon^2}, T ≳ ε 2 k log N + log ( 1/ δ ) ,
then, with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≤ A C ( β ) for every β ∈ R k . \lvert\operatorname{Err}_C(\beta) \rvert\le A_C(\beta) \qquad\text{for every } \beta\in\mathbb{R}^k. ∣ Err C ( β )∣ ≤ A C ( β ) for every β ∈ R k .
Proof of Theorem 5.1 . Apply Lemma 5.7 to each fixed C ∈ X k C \in X^k C ∈ X k with failure probability δ / N k \delta/N^k δ / N k . Since there are at most N k N^k N k center tuples, a union bound gives, with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≤ A C ( β ) for every C ∈ X k and every β ∈ R k . \lvert\operatorname{Err}_C(\beta) \rvert\le A_C(\beta) \qquad\text{for every } C \in X^k \text{ and every } \beta\in\mathbb{R}^k. ∣ Err C ( β )∣ ≤ A C ( β ) for every C ∈ X k and every β ∈ R k .
On this event, Lemma 5.6 gives
cost ~ Q ( C , h ) = ( 1 ± O ( ε ) ) cost ~ P ( C , h ) for every C ∈ X k and every h ∈ n Δ k . \widetilde{\operatorname{cost}}_Q(C,h) = (1 \pm O(\varepsilon))\widetilde{\operatorname{cost}}_P(C,h) \qquad\text{for every } C \in X^k \text{ and every } h \in n\Delta_k. cost Q ( C , h ) = ( 1 ± O ( ε )) cost P ( C , h ) for every C ∈ X k and every h ∈ n Δ k .
It remains to pass from truncated costs to the original costs. By Lemma 5.4 , applied to both P P P and Q Q Q ,
cost ~ P ( C , h ) = ( 1 ± O ( ε ) ) cost P ( C , h ) , cost ~ Q ( C , h ) = ( 1 ± O ( ε ) ) cost Q ( C , h ) . \widetilde{\operatorname{cost}}_P(C,h) = (1 \pm O(\varepsilon))\operatorname{cost}_P(C,h), \qquad\widetilde{\operatorname{cost}}_Q(C,h) = (1 \pm O(\varepsilon))\operatorname{cost}_Q(C,h). cost P ( C , h ) = ( 1 ± O ( ε )) cost P ( C , h ) , cost Q ( C , h ) = ( 1 ± O ( ε )) cost Q ( C , h ) .
Combining these, we have
cost Q ( C , h ) = ( 1 ± O ( ε ) ) cost P ( C , h ) \operatorname{cost}_Q(C,h) = (1 \pm O(\varepsilon))\operatorname{cost}_P(C,h) cost Q ( C , h ) = ( 1 ± O ( ε )) cost P ( C , h )
simultaneously for every C ∈ X k C \in X^k C ∈ X k and every h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k . Rescaling ε \varepsilon ε by a sufficiently small constant gives the claimed ε \varepsilon ε -coreset guarantee. □
The rest of the section proves Lemma 5.4 , Lemma 5.6 , and Lemma 5.7 .
Truncated Costs Approximate True Costs: Proof of Lemma 5.4
We now show that the truncated objective is equivalent to the original squared-distance objective. The reason is simple: if a point-center cost is truncated, the center is far enough from the ring that every point in the ring has nearly the same squared distance to it as the anchor does.
Lemma 5.4 (Truncation comparison). For every weighted ring-labelled instance S S S , every center tuple C ∈ X k C \in X^k C ∈ X k , and every demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
cost ~ S ( C , h ) = ( 1 ± O ( ε ) ) cost S ( C , h ) . \widetilde{\operatorname{cost}}_S(C,h) = (1 \pm O(\varepsilon))\operatorname{cost}_S(C,h). cost S ( C , h ) = ( 1 ± O ( ε )) cost S ( C , h ) .
Proof. Fix a weighted instance S S S supported on P P P , a center tuple C C C , and a demand vector h h h . We first show that, for every point p p p and center c i c_i c i ,
ℓ ~ i ( p ) = ( 1 ± O ( ε ) ) d ( p , c i ) 2 . (7) \widetilde{\ell}_i(p) = (1 \pm O(\varepsilon))d(p,c_i)^2. \tag*{(7)} ℓ i ( p ) = ( 1 ± O ( ε )) d ( p , c i ) 2 . (7)
If the cost of assigning p p p to c i c_i c i is not truncated, then ℓ ~ i ( p ) = d ( p , c i ) 2 \widetilde{\ell}_i(p)=d(p,c_i)^2 ℓ i ( p ) = d ( p , c i ) 2 and there is nothing to prove. If it is truncated, then ℓ ~ i ( p ) = d ( a R , c i ) 2 \widetilde{\ell}_i(p)=d(a_R,c_i)^2 ℓ i ( p ) = d ( a R , c i ) 2 and d ( a R , c i ) > ρ R / ε d(a_R,c_i)>\rho_R/\varepsilon d ( a R , c i ) > ρ R / ε . Since d ( p , a R ) ≤ ρ R d(p,a_R)\leq\rho_R d ( p , a R ) ≤ ρ R , we have d ( p , a R ) ≤ ε d ( a R , c i ) d(p,a_R)\leq\varepsilon d(a_R,c_i) d ( p , a R ) ≤ ε d ( a R , c i ) . Hence, by the triangle inequality, d ( p , c i ) = ( 1 ± O ( ε ) ) d ( a R , c i ) d(p,c_i)=(1\pm O(\varepsilon))d(a_R,c_i) d ( p , c i ) = ( 1 ± O ( ε )) d ( a R , c i ) , and therefore
d ( p , c i ) 2 = ( 1 ± O ( ε ) ) d ( a R , c i ) 2 = ( 1 ± O ( ε ) ) ℓ ~ i ( p ) . d(p,c_i)^2=(1\pm O(\varepsilon))d(a_R,c_i)^2=(1\pm O(\varepsilon))\widetilde{\ell}_i(p). d ( p , c i ) 2 = ( 1 ± O ( ε )) d ( a R , c i ) 2 = ( 1 ± O ( ε )) ℓ i ( p ) .
This proves (7) after adjusting the implicit constant.
Now take any feasible fractional assignment x x x for S S S with load vector h h h . Since x p , i ≥ 0 x_{p,i}\geq0 x p , i ≥ 0 , summing (7) over all assigned pairs ( p , i ) (p,i) ( p , i ) gives
∑ p , i x p , i ℓ ~ i ( p ) = ( 1 ± O ( ε ) ) ∑ p , i x p , i d ( p , c i ) 2 . \sum_{p,i}x_{p,i}\widetilde{\ell}_i(p)=(1\pm O(\varepsilon))\sum_{p,i}x_{p,i}d(p,c_i)^2. p , i ∑ x p , i ℓ i ( p ) = ( 1 ± O ( ε )) p , i ∑ x p , i d ( p , c i ) 2 .
Applying this once to an optimal assignment for cost S ( C , h ) \operatorname{cost}_S(C,h) cost S ( C , h ) and once to an optimal assignment for cost S ~ ( C , h ) \operatorname{cost}_{\widetilde{S}}(C,h) cost S ( C , h ) gives
cost ~ S ( C , h ) = ( 1 ± O ( ε ) ) cost S ( C , h ) . \widetilde{\operatorname{cost}}_S(C,h)=(1\pm O(\varepsilon))\operatorname{cost}_S(C,h). cost S ( C , h ) = ( 1 ± O ( ε )) cost S ( C , h ) .
From Dual Error to Cost Preservation: Proof of Lemma 5.6
We prove that controlling the dual sampling error by the allowed error A C ( β ) A_C(\beta) A C ( β ) is enough to preserve the truncated assignment cost for every demand vector.
Lemma 5.6 (Allowed-error dual preservation). Fix C ∈ X k C\in X^k C ∈ X k . Suppose that
∣ Err C ( β ) ∣ ≤ A C ( β ) for every β ∈ R k . |\operatorname{Err}_C(\beta)|\leq A_C(\beta)\qquad\text{for every }\beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≤ A C ( β ) for every β ∈ R k . Then, for every demand vector h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k ,
cost ~ Q ( C , h ) = ( 1 ± O ( ε ) ) cost ~ P ( C , h ) . \widetilde{\operatorname{cost}}_Q(C,h)=(1\pm O(\varepsilon))\widetilde{\operatorname{cost}}_P(C,h). cost Q ( C , h ) = ( 1 ± O ( ε )) cost P ( C , h ) .
Proof. Fix h ∈ n Δ k h\in n\Delta_k h ∈ n Δ k . For the upper bound, for every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k ,
Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + A C ( β ) . \operatorname{Dual}_Q(C,h,\beta)\leq\operatorname{Dual}_P(C,h,\beta)+A_C(\beta). Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + A C ( β ) .
By the definition of A C ( β ) A_C(\beta) A C ( β ) ,
A C ( β ) ≤ ε cost ~ P ( C , h ) + 1 4 Δ C , h ( β ) . A_C(\beta)\leq\varepsilon\widetilde{\operatorname{cost}}_P(C,h)+\frac{1}{4}\Delta_{C,h}(\beta). A C ( β ) ≤ ε cost P ( C , h ) + 4 1 Δ C , h ( β ) .
Therefore,
Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + ε cost ~ P ( C , h ) + 1 4 ( cost ~ P ( C , h ) − Dual P ( C , h , β ) ) = 3 4 Dual P ( C , h , β ) + ( 1 4 + ε ) cost ~ P ( C , h ) ≤ ( 1 + ε ) cost ~ P ( C , h ) , \begin{aligned}
\operatorname{Dual}_Q(C,h,\beta)
&\leq\operatorname{Dual}_P(C,h,\beta)+\varepsilon\widetilde{\operatorname{cost}}_P(C,h)\\
&\quad+\frac{1}{4}\bigl(\widetilde{\operatorname{cost}}_P(C,h)-\operatorname{Dual}_P(C,h,\beta)\bigr)\\
&=\frac{3}{4}\operatorname{Dual}_P(C,h,\beta)+\left(\frac{1}{4}+\varepsilon\right)\widetilde{\operatorname{cost}}_P(C,h)\\
&\leq(1+\varepsilon)\widetilde{\operatorname{cost}}_P(C,h),
\end{aligned} Dual Q ( C , h , β ) ≤ Dual P ( C , h , β ) + ε cost P ( C , h ) + 4 1 ( cost P ( C , h ) − Dual P ( C , h , β ) ) = 4 3 Dual P ( C , h , β ) + ( 4 1 + ε ) cost P ( C , h ) ≤ ( 1 + ε ) cost P ( C , h ) ,
where the last inequality uses Dual P ( C , h , β ) ≤ cost ~ P ( C , h ) \operatorname{Dual}_{P}(C,h,\beta) \le\widetilde{\operatorname{cost}}_{P}(C,h) Dual P ( C , h , β ) ≤ cost P ( C , h ) .
Taking the supremum over β \beta β gives
cost ~ Q ( C , h ) ≤ ( 1 + ε ) cost ~ P ( C , h ) . \widetilde{\operatorname{cost}}_{Q}(C,h) \le(1+\varepsilon)\widetilde{\operatorname{cost}}_{P}(C,h). cost Q ( C , h ) ≤ ( 1 + ε ) cost P ( C , h ) .
For the lower bound, let β ⋆ \beta^{\star} β ⋆ be an optimal dual solution for cost ~ P ( C , h ) \widetilde{\operatorname{cost}}_{P}(C,h) cost P ( C , h ) . Then Δ C , h ( β ⋆ ) = 0 \Delta_{C,h}(\beta^{\star})=0 Δ C , h ( β ⋆ ) = 0 , and hence
A C ( β ⋆ ) ≤ ε cost ~ P ( C , h ) . A_C(\beta^{\star}) \le\varepsilon\widetilde{\operatorname{cost}}_{P}(C,h). A C ( β ⋆ ) ≤ ε cost P ( C , h ) .
Thus
cost ~ Q ( C , h ) ≥ Dual Q ( C , h , β ⋆ ) ≥ Dual P ( C , h , β ⋆ ) − A C ( β ⋆ ) ≥ ( 1 − ε ) cost ~ P ( C , h ) . \widetilde{\operatorname{cost}}_{Q}(C,h) \ge\operatorname{Dual}_{Q}(C,h,\beta^{\star}) \ge\operatorname{Dual}_{P}(C,h,\beta^{\star}) - A_C(\beta^{\star}) \ge(1-\varepsilon)\widetilde{\operatorname{cost}}_{P}(C,h). cost Q ( C , h ) ≥ Dual Q ( C , h , β ⋆ ) ≥ Dual P ( C , h , β ⋆ ) − A C ( β ⋆ ) ≥ ( 1 − ε ) cost P ( C , h ) .
Weak Dual Convergence: Proof of Lemma 5.7
The proof of weak dual convergence is the technical core of the k k k -means analysis. We prove the statement for a fixed center tuple C C C , uniformly over all dual vectors β \beta β . The extension to all C ∈ X k C \in X^k C ∈ X k is then obtained by a union bound in the proof of Theorem 5.1 .
The proof has two internal ingredients. First, a localized concentration bound shows that, for one fixed dual vector, the sampling error is controlled at the allowed-error scale. Second, a discretization argument reduces the infinite family of dual vectors to a finite representative set. The point of the localized argument is that near-optimal dual vectors are controlled accurately, while dual vectors with large dual gap may be controlled more coarsely.
The first ingredient gives the desired allowed-error bound for one fixed dual vector.
Lemma 5.8 (Pointwise concentration). Fix C ∈ X k C \in X^k C ∈ X k , β ∈ R k \beta\in\mathbb{R}^k β ∈ R k , and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . If
T ≥ log ( 1 / δ ) ε 2 , T \ge\frac{\log(1/\delta)}{\varepsilon^2}, T ≥ ε 2 log ( 1/ δ ) , then
∣ Err C ( β ) ∣ ≤ 1 8 A C ( β ) |\operatorname{Err}_C(\beta)| \le\frac{1}{8}A_C(\beta) ∣ Err C ( β ) ∣ ≤ 8 1 A C ( β ) with probability at least 1 − δ 1-\delta 1 − δ .
The second ingredient upgrades control on finitely many representative dual vectors to control over all β ∈ R k \beta\in\mathbb{R}^k β ∈ R k .
Lemma 5.9 (Dual-vector discretization). Fix C ∈ X k C \in X^k C ∈ X k . There is a set B C ⊆ R k \mathcal{B}_C \subseteq\mathbb{R}^k B C ⊆ R k of size
∣ B C ∣ ≤ exp { O ( k log ( N / ε ) ) } |\mathcal{B}_C| \le\exp\{O(k\log(N/\varepsilon))\} ∣ B C ∣ ≤ exp { O ( k log ( N / ε ))} such that the following implication holds. If
∣ Err C ( β ) ∣ ≤ 1 8 A C ( β ) ∀ β ∈ B C , |\operatorname{Err}_C(\beta)| \le\frac{1}{8}A_C(\beta) \qquad\forall\beta\in\mathcal{B}_C, ∣ Err C ( β ) ∣ ≤ 8 1 A C ( β ) ∀ β ∈ B C , then
∣ Err C ( β ) ∣ ≤ A C ( β ) ∀ β ∈ R k . |\operatorname{Err}_C(\beta)| \le A_C(\beta) \qquad\forall\beta\in\mathbb{R}^k. ∣ Err C ( β ) ∣ ≤ A C ( β ) ∀ β ∈ R k .
With the two lemmas in hand, we can state and prove the uniform convergence for all dual vectors. We return to the proofs of the lemmas after that.
Lemma 5.7 (Uniform weak dual convergence for fixed centers). Fix C ∈ X k C \in X^k C ∈ X k . If
T ≳ k log N + log ( 1 / δ ) ε 2 , T \gtrsim\frac{k \log N + \log(1/\delta)}{\varepsilon^2}, T ≳ ε 2 k log N + log ( 1/ δ ) , then, with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≤ A C ( β ) for every β ∈ R k . \lvert\operatorname{Err}_C(\beta) \rvert\le A_C(\beta) \qquad\text{for every } \beta\in\mathbb{R}^k. ∣ Err C ( β )∣ ≤ A C ( β ) for every β ∈ R k . Proof. Fix C ∈ X k C \in X^k C ∈ X k , and let B C \mathcal{B}_C B C be the representative set from Lemma 5.9 . Apply Lemma 5.8 to every β ∈ B C \beta\in\mathcal{B}_C β ∈ B C , using failure probability
δ ′ = δ ∣ B C ∣ . \delta' = \frac{\delta}{\lvert\mathcal{B}_C\rvert}. δ ′ = ∣ B C ∣ δ . By a union bound over B C \mathcal{B}_C B C , with probability at least 1 − δ 1-\delta 1 − δ ,
∣ Err C ( β ) ∣ ≤ 1 8 A C ( β ) ∀ β ∈ B C , \lvert\operatorname{Err}_C(\beta) \rvert\le\frac{1}{8} A_C(\beta) \qquad\forall\beta\in\mathcal{B}_C, ∣ Err C ( β )∣ ≤ 8 1 A C ( β ) ∀ β ∈ B C , provided
T ≳ k log N + log ( 1 / δ ) ε 2 . T \gtrsim\frac{k \log N + \log(1/\delta)}{\varepsilon^2}. T ≳ ε 2 k log N + log ( 1/ δ ) . On this event, Lemma 5.9 gives
∣ Err C ( β ) ∣ ≤ A C ( β ) ∀ β ∈ R k . \lvert\operatorname{Err}_C(\beta) \rvert\le A_C(\beta) \qquad\forall\beta\in\mathbb{R}^k. ∣ Err C ( β )∣ ≤ A C ( β ) ∀ β ∈ R k . This proves Lemma 5.7 .
Pointwise concentration
We prove Lemma 5.8 . Throughout this subsection, fix a center tuple C ∈ X k C \in X^k C ∈ X k and a dual vector β ∈ R k \beta\in\mathbb{R}^k β ∈ R k .
For a ring R R R , define
g R ( p ) = f C , β ( p ) − f C , β ( a R ) , g ˉ R = 1 n R ∑ p ∈ R g R ( p ) . g_R(p) = f_{C,\beta}(p) - f_{C,\beta}(a_R), \qquad\bar{g}_R = \frac{1}{n_R}\sum_{p \in R} g_R(p). g R ( p ) = f C , β ( p ) − f C , β ( a R ) , g ˉ R = n R 1 p ∈ R ∑ g R ( p ) .
The truncation step gives the centered range bound
∣ g R ( p ) ∣ ≲ ε − 1 ρ R 2 for every p ∈ R . (8) \lvert g_R(p) \rvert\lesssim\varepsilon^{-1}\rho_R^2 \qquad\text{for every } p \in R. \tag*{(8)} ∣ g R ( p )∣ ≲ ε − 1 ρ R 2 for every p ∈ R . (8)
We also use the following variance-gap estimate, proved in the next subsection.
Lemma 5.10 (Variance-gap estimate). Fix C ∈ X k C \in X^k C ∈ X k , h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k , and β ∈ R k \beta\in\mathbb{R}^k β ∈ R k . Then
∑ R ∈ R n R ρ R 2 Var p ∼ R [ g R ( p ) ] ≤ O ( cost ^ P ( C , h ) + ε − 1 Δ C , h ( β ) ) . \sum_{R \in\mathcal{R}} \frac{n_R}{\rho_R^2}\operatorname{Var}_{p\sim R}[g_R(p)] \le O\left(\widehat{\operatorname{cost}}_P(C,h) + \varepsilon^{-1}\Delta_{C,h}(\beta)\right). R ∈ R ∑ ρ R 2 n R Var p ∼ R [ g R ( p )] ≤ O ( cost P ( C , h ) + ε − 1 Δ C , h ( β ) ) .
This estimate says that large within-ring variance can occur only for dual vectors with large dual gap. Such vectors have a larger allowed error in A C ( β ) A_C(\beta) A C ( β ) , which is exactly what Bernstein concentration exploits.
Proof of Lemma 5.8. Let h ⋆ ∈ n Δ k h^\star\in n\Delta_k h ⋆ ∈ n Δ k attain the infimum in the definition of A C ( β ) A_C(\beta) A C ( β ) , and write
U = cost ~ P ( C , h ⋆ ) , D = Δ C , h ⋆ ( β ) . U = \widetilde{\operatorname{cost}}_P(C,h^\star), \qquad D = \Delta_{C,h^\star}(\beta). U = cost P ( C , h ⋆ ) , D = Δ C , h ⋆ ( β ) .
Thus
A C ( β ) = ε U + 1 4 D . A_C(\beta) = \varepsilon U + \frac{1}{4}D. A C ( β ) = ε U + 4 1 D .
For each ring R R R , let q R , 1 , … , q R , m R q_{R,1},\ldots,q_{R,m_R} q R , 1 , … , q R , m R be the independent uniform samples from R R R . Since the sampled points from R R R have total weight exactly n R n_R n R , the anchor contribution cancels. Hence
Err C ( β ) = ∑ R ∈ R n R ( 1 m R ∑ t = 1 m R g R ( q R , t ) − g ˉ R ) . (9) \operatorname{Err}_C(\beta) = \sum_{R\in\mathcal{R}} n_R\left(\frac{1}{m_R}\sum_{t=1}^{m_R}g_R(q_{R,t})-\bar g_R\right). \tag*{(9)} Err C ( β ) = R ∈ R ∑ n R ( m R 1 t = 1 ∑ m R g R ( q R , t ) − g ˉ R ) . (9)
Equivalently,
Err C ( β ) = ∑ R ∈ R ∑ t = 1 m R Z R , t , Z R , t = n R m R ( g R ( q R , t ) − g ˉ R ) . \operatorname{Err}_C(\beta) = \sum_{R\in\mathcal{R}}\sum_{t=1}^{m_R} Z_{R,t}, \qquad Z_{R,t}=\frac{n_R}{m_R}\left(g_R(q_{R,t})-\bar g_R\right). Err C ( β ) = R ∈ R ∑ t = 1 ∑ m R Z R , t , Z R , t = m R n R ( g R ( q R , t ) − g ˉ R ) .
The variables Z R , t Z_{R,t} Z R , t are independent and mean zero. We now record the two quantities needed for Bernstein’s inequality. First, using the sampling rule
m R ≳ T n R ρ R 2 W 2 , m_R \gtrsim T\frac{n_R\rho_R^2}{W_2}, m R ≳ T W 2 n R ρ R 2 ,
we have
∑ R , t E [ Z R , t 2 ] = ∑ R ∈ R n R 2 m R Var p ∼ R [ g R ( p ) ] ≤ O ( W 2 T ∑ R ∈ R n R ρ R 2 Var p ∼ R [ g R ( p ) ] ) . \sum_{R,t}\mathbb{E}[Z_{R,t}^2]
=\sum_{R\in\mathcal{R}}\frac{n_R^2}{m_R}\operatorname{Var}_{p\sim R}[g_R(p)]
\leq O\left(\frac{W_2}{T}\sum_{R\in\mathcal{R}}\frac{n_R}{\rho_R^2}\operatorname{Var}_{p\sim R}[g_R(p)]\right). R , t ∑ E [ Z R , t 2 ] = R ∈ R ∑ m R n R 2 Var p ∼ R [ g R ( p )] ≤ O ( T W 2 R ∈ R ∑ ρ R 2 n R Var p ∼ R [ g R ( p )] ) .
By Lemma 5.10, applied with h = h ⋆ h=h^\star h = h ⋆ , and since W 2 ≲ U W_2\lesssim U W 2 ≲ U ,
V : = ∑ R , t E [ Z R , t 2 ] ≤ O ( U T ( U + ε − 1 D ) ) . (10) V:=\sum_{R,t}\mathbb{E}[Z_{R,t}^2]\leq O\left(\frac{U}{T}\left(U+\varepsilon^{-1}D\right)\right). \tag*{(10)} V := R , t ∑ E [ Z R , t 2 ] ≤ O ( T U ( U + ε − 1 D ) ) . (10)
Second, by (8),
∣ g R ( q R , t ) − g ˉ R ∣ ≲ ε − 1 ρ R 2 . \left|g_R(q_{R,t})-\bar g_R\right|\lesssim\varepsilon^{-1}\rho_R^2. ∣ g R ( q R , t ) − g ˉ R ∣ ≲ ε − 1 ρ R 2 .
Using the sampling rule again and W 2 ≲ U W_2\lesssim U W 2 ≲ U , we get
M : = max R , t ∣ Z R , t ∣ ≤ O ( ε − 1 U T ) . (11) M:=\max_{R,t}|Z_{R,t}|\leq O\left(\frac{\varepsilon^{-1}U}{T}\right). \tag*{(11)} M := R , t max ∣ Z R , t ∣ ≤ O ( T ε − 1 U ) . (11)
Using Bernstein’s inequality (see Lemma B.2) applied to the independent mean-zero variables Z R , t Z_{R,t} Z R , t ,
∣ Err C ( β ) ∣ ≲ V log ( 1 / δ ) + M log ( 1 / δ ) |\operatorname{Err}_C(\beta)|\lesssim\sqrt{V\log(1/\delta)}+M\log(1/\delta) ∣ Err C ( β ) ∣ ≲ V log ( 1/ δ ) + M log ( 1/ δ )
with probability at least 1 − δ 1-\delta 1 − δ , where
V = ∑ R , t E [ Z R , t 2 ] , M = max R , t ∣ Z R , t ∣ . V=\sum_{R,t}\mathbb{E}[Z_{R,t}^2], \qquad M=\max_{R,t}|Z_{R,t}|. V = R , t ∑ E [ Z R , t 2 ] , M = R , t max ∣ Z R , t ∣.
Substituting (10) and (11) , we obtain
∣ Err C ( β ) ∣ ≲ U T ( U + ε − 1 D ) log ( 1 / δ ) + ε − 1 U T log ( 1 / δ ) . \lvert\operatorname{Err}_{C}(\beta) \rvert\lesssim\sqrt{\frac{U}{T}(U+\varepsilon^{-1}D)\log(1/\delta)}+\frac{\varepsilon^{-1}U}{T}\log(1/\delta). ∣ Err C ( β )∣ ≲ T U ( U + ε − 1 D ) log ( 1/ δ ) + T ε − 1 U log ( 1/ δ ) .
If T ≳ log ( 1 / δ ) ε 2 T \gtrsim\frac{\log(1/\delta)}{\varepsilon^2} T ≳ ε 2 l o g ( 1/ δ ) , then the second term is at most O ( ε U ) O(\varepsilon U) O ( ε U ) , with an arbitrarily small implicit constant after increasing the constant in the lower bound on T T T . The same assumption gives
U T ( U + ε − 1 D ) log ( 1 / δ ) ≲ ε U ( U + ε − 1 D ) ≲ ε U + D , \sqrt{\frac{U}{T}(U+\varepsilon^{-1}D)\log(1/\delta)}\lesssim\varepsilon\sqrt{U(U+\varepsilon^{-1}D)}\lesssim\varepsilon U+D, T U ( U + ε − 1 D ) log ( 1/ δ ) ≲ ε U ( U + ε − 1 D ) ≲ ε U + D ,
again with an arbitrarily small implicit constant after increasing the constant in the lower bound on T T T . Therefore,
∣ Err C ( β ) ∣ ≤ 1 8 ( ε U + 1 4 D ) = 1 8 A C ( β ) . \lvert\operatorname{Err}_{C}(\beta) \rvert\leq\frac{1}{8}\left(\varepsilon U+\frac{1}{4}D\right)=\frac{1}{8}A_C(\beta). ∣ Err C ( β )∣ ≤ 8 1 ( ε U + 4 1 D ) = 8 1 A C ( β ) .
This proves the claim.
Proof of the variance-gap estimate
We now prove the variance bound in Lemma 5.10 . This lemma provides the variance term needed for Bernstein’s inequality: although the worst-case within-ring variation of the truncated dual function can be as large as O ( ε − 1 ρ R 2 ) O(\varepsilon^{-1}\rho_R^2) O ( ε − 1 ρ R 2 ) , its aggregate variance is much smaller, namely controlled by
cost ~ P ( C , h ) + ε − 1 Δ C , h ( β ) . \widetilde{\operatorname{cost}}_P(C,h)+\varepsilon^{-1}\Delta_{C,h}(\beta). cost P ( C , h ) + ε − 1 Δ C , h ( β ) .
Consequently, when the duality gap is small, Bernstein concentration occurs at the scale of the clustering cost rather than at the scale suggested by the worst-case range bound alone.
Fix C , h , β C,h,\beta C , h , β . The function
f C , β ( p ) = min i { ℓ ~ i ( p ) + β i } f_{C,\beta}(p)=\min_i\{\widetilde{\ell}_i(p)+\beta_i\} f C , β ( p ) = i min { ℓ i ( p ) + β i }
chooses, for each point p p p , the best β \beta β -shifted center. This minimizing center may change from point to point, so we compare it to the optimal primal assignment for the fixed demand vector h h h . Let x ∗ x^* x ∗ be an optimal assignment attaining cost ~ P ( C , h ) \widetilde{\operatorname{cost}}_P(C,h) cost P ( C , h ) .
For p ∈ P p\in P p ∈ P and i ∈ [ k ] i\in[k] i ∈ [ k ] , define the slack
s p , i = ℓ ~ i ( p ) + β i − f C , β ( p ) . (12) s_{p,i}=\widetilde{\ell}_i(p)+\beta_i-f_{C,\beta}(p). \tag*{(12)} s p , i = ℓ i ( p ) + β i − f C , β ( p ) . (12)
Thus s p , i s_{p,i} s p , i measures how far center i i i is from being a minimizer in the definition of f C , β ( p ) f_{C,\beta}(p) f C , β ( p ) . Since f C , β ( p ) = min i { ℓ ~ i ( p ) + β i } f_{C,\beta}(p)=\min_i\{\widetilde{\ell}_i(p)+\beta_i\} f C , β ( p ) = min i { ℓ i ( p ) + β i } , we have s p , i ≥ 0 s_{p,i}\geq0 s p , i ≥ 0 for every p p p and i i i .
The point of this definition is that the duality gap is exactly the total slack incurred by the optimal primal assignment x ∗ x^* x ∗ :
Δ C , h ( β ) = ∑ p ∈ P ∑ i = 1 k x p , i ∗ s p , i . (13) \Delta_{C,h}(\beta)=\sum_{p\in P}\sum_{i=1}^{k}x^*_{p,i}s_{p,i}. \tag*{(13)} Δ C , h ( β ) = p ∈ P ∑ i = 1 ∑ k x p , i ∗ s p , i . (13)
Indeed, using the optimality of x ∗ x^* x ∗ for cost ~ P ( C , h ) \widetilde{\operatorname{cost}}_P(C,h) cost P ( C , h ) and the definition of the dual objective,
Δ C , h ( β ) = cost ~ P ( C , h ) − Dual P ( C , h , β ) = ∑ p , i x p , i ∗ ℓ ~ i ( p ) − ∑ p ∈ P f C , β ( p ) + ∑ i = 1 k h i β i = ∑ p , i x p , i ∗ ( ℓ ~ i ( p ) + β i − f C , β ( p ) ) = ∑ p , i x p , i ∗ s p , i . \begin{aligned}
\Delta_{C,h}(\beta)
&=\widetilde{\operatorname{cost}}_P(C,h)-\operatorname{Dual}_P(C,h,\beta)\\
&=\sum_{p,i}x^*_{p,i}\widetilde{\ell}_i(p)-\sum_{p\in P}f_{C,\beta}(p)+\sum_{i=1}^{k}h_i\beta_i\\
&=\sum_{p,i}x^*_{p,i}\left(\widetilde{\ell}_i(p)+\beta_i-f_{C,\beta}(p)\right)=\sum_{p,i}x^*_{p,i}s_{p,i}.
\end{aligned} Δ C , h ( β ) = cost P ( C , h ) − Dual P ( C , h , β ) = p , i ∑ x p , i ∗ ℓ i ( p ) − p ∈ P ∑ f C , β ( p ) + i = 1 ∑ k h i β i = p , i ∑ x p , i ∗ ( ℓ i ( p ) + β i − f C , β ( p ) ) = p , i ∑ x p , i ∗ s p , i .
which proves (13) .
The last step follows from the fact that we have,
∑ i x p , i ⋆ = 1 for every p , and ∑ p x p , i ⋆ = h i for every i . \sum_i x^\star_{p,i}=1 \qquad\text{for every }p,\qquad\text{and}\qquad\sum_p x^\star_{p,i}=h_i \qquad\text{for every }i. i ∑ x p , i ⋆ = 1 for every p , and p ∑ x p , i ⋆ = h i for every i .
For a ring R R R , let
cost ~ R = ∑ p ∈ R ∑ i = 1 k x p , i ⋆ ℓ ~ i ( p ) , G R = ∑ p ∈ R ∑ i = 1 k x p , i ⋆ s p , i . \widetilde{\operatorname{cost}}_R=\sum_{p\in R}\sum_{i=1}^{k}x^\star_{p,i}\widetilde{\ell}_i(p),\qquad G_R=\sum_{p\in R}\sum_{i=1}^{k}x^\star_{p,i}s_{p,i}. cost R = p ∈ R ∑ i = 1 ∑ k x p , i ⋆ ℓ i ( p ) , G R = p ∈ R ∑ i = 1 ∑ k x p , i ⋆ s p , i .
Thus
∑ R cost ~ R = cost ~ P ( C , h ) , ∑ R G R = Δ C , h ( β ) . \sum_R\widetilde{\operatorname{cost}}_R=\widetilde{\operatorname{cost}}_P(C,h),\qquad\sum_R G_R=\Delta_{C,h}(\beta). R ∑ cost R = cost P ( C , h ) , R ∑ G R = Δ C , h ( β ) .
We now bound the variance inside a ring R R R . Since subtracting the anchor value does not change variance,
Var p ∼ R [ g R ( p ) ] = Var p ∼ R [ f C , β ( p ) ] = 1 2 E p , q ∼ R ( f C , β ( p ) − f C , β ( q ) ) 2 . \operatorname{Var}_{p\sim R}[g_R(p)]=\operatorname{Var}_{p\sim R}[f_{C,\beta}(p)]=\frac{1}{2}\mathbb{E}_{p,q\sim R}\left(f_{C,\beta}(p)-f_{C,\beta}(q)\right)^2. Var p ∼ R [ g R ( p )] = Var p ∼ R [ f C , β ( p )] = 2 1 E p , q ∼ R ( f C , β ( p ) − f C , β ( q ) ) 2 .
Thus it is enough to control the squared fluctuation of f C , β f_{C,\beta} f C , β on pairs of points in R R R . The purpose of the next estimate is to express this fluctuation as the sum of two terms: a truncated-cost variation term, which will be charged to cost ~ R \widetilde{\operatorname{cost}}_R cost R , and a slack term, which will be charged to G R G_R G R .
Fix p , q ∈ R p,q\in R p , q ∈ R , and write
D = ∣ f C , β ( p ) − f C , β ( q ) ∣ . D=\left|f_{C,\beta}(p)-f_{C,\beta}(q)\right|. D = ∣ f C , β ( p ) − f C , β ( q ) ∣ .
First suppose that f C , β ( p ) ≥ f C , β ( q ) f_{C,\beta}(p)\ge f_{C,\beta}(q) f C , β ( p ) ≥ f C , β ( q ) . Then, using s p , i , s q , i ≥ 0 s_{p,i},s_{q,i}\ge0 s p , i , s q , i ≥ 0 , for every i ∈ [ k ] i\in[k] i ∈ [ k ] ,
D = f C , β ( p ) − f C , β ( q ) = ℓ ~ i ( p ) − ℓ ~ i ( q ) − s p , i + s q , i ≤ ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ + s q , i . \begin{aligned}
D&=f_{C,\beta}(p)-f_{C,\beta}(q)\\
&=\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)-s_{p,i}+s_{q,i}\\
&\le\left|\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\right|+s_{q,i}.
\end{aligned} D = f C , β ( p ) − f C , β ( q ) = ℓ i ( p ) − ℓ i ( q ) − s p , i + s q , i ≤ ℓ i ( p ) − ℓ i ( q ) + s q , i .
Also, by the centered range bound,
D = ∣ g R ( p ) − g R ( q ) ∣ ≲ ε − 1 ρ R 2 . D=\left|g_R(p)-g_R(q)\right|\lesssim\varepsilon^{-1}\rho_R^2. D = ∣ g R ( p ) − g R ( q ) ∣ ≲ ε − 1 ρ R 2 .
Combining these inequalities, we get, for every i ∈ [ k ] i\in[k] i ∈ [ k ] ,
D 2 ≲ ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 + ρ R 2 ε s q , i . D^2\lesssim\left|\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\right|^2+\frac{\rho_R^2}{\varepsilon}s_{q,i}. D 2 ≲ ℓ i ( p ) − ℓ i ( q ) 2 + ε ρ R 2 s q , i .
Indeed, apply the elementary implication
0 ≤ D ≤ A + s , D ≤ B ⟹ D 2 ≲ A 2 + B s 0\le D\le A+s,\qquad D\le B\qquad\Longrightarrow\qquad D^2\lesssim A^2+Bs 0 ≤ D ≤ A + s , D ≤ B ⟹ D 2 ≲ A 2 + B s
with
A = ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ , B ≲ ε − 1 ρ R 2 , s = s q , i . A=\left|\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\right|,\qquad B\lesssim\varepsilon^{-1}\rho_R^2,\qquad s=s_{q,i}. A = ℓ i ( p ) − ℓ i ( q ) , B ≲ ε − 1 ρ R 2 , s = s q , i .
Averaging this inequality over i i i with weights x q , i ⋆ x^\star_{q,i} x q , i ⋆ , and using
∑ i x q , i ⋆ = 1 , \sum_i x^\star_{q,i}=1, i ∑ x q , i ⋆ = 1 ,
gives
D 2 ≲ ∑ i x q , i ⋆ ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 + ρ R 2 ε ∑ i x q , i ⋆ s q , i . D^2 \lesssim\sum_i x_{q,i}^\star\lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2+\frac{\rho_R^2}{\varepsilon}\sum_i x_{q,i}^\star s_{q,i}. D 2 ≲ i ∑ x q , i ⋆ ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2 + ε ρ R 2 i ∑ x q , i ⋆ s q , i .
The case f C , β ( q ) > f C , β ( p ) f_{C,\beta}(q)>f_{C,\beta}(p) f C , β ( q ) > f C , β ( p ) is symmetric. In that case, the same argument gives
D 2 ≲ ∑ i x p , i ⋆ ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 + ρ R 2 ε ∑ i x p , i ⋆ s p , i . D^2 \lesssim\sum_i x_{p,i}^\star\lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2+\frac{\rho_R^2}{\varepsilon}\sum_i x_{p,i}^\star s_{p,i}. D 2 ≲ i ∑ x p , i ⋆ ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2 + ε ρ R 2 i ∑ x p , i ⋆ s p , i .
Combining the two cases, and upper bounding D 2 D^2 D 2 by the sum of the two bounds, we obtain
( f C , β ( p ) − f C , β ( q ) ) 2 ≲ ∑ i ( x p , i ⋆ + x q , i ⋆ ) ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 + ρ R 2 ε ∑ i ( x p , i ⋆ s p , i + x q , i ⋆ s q , i ) . \left(f_{C,\beta}(p)-f_{C,\beta}(q)\right)^2\lesssim\sum_i\left(x_{p,i}^\star+x_{q,i}^\star\right)\lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2
+\frac{\rho_R^2}{\varepsilon}\sum_i\left(x_{p,i}^\star s_{p,i}+x_{q,i}^\star s_{q,i}\right). ( f C , β ( p ) − f C , β ( q ) ) 2 ≲ i ∑ ( x p , i ⋆ + x q , i ⋆ ) ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2 + ε ρ R 2 i ∑ ( x p , i ⋆ s p , i + x q , i ⋆ s q , i ) .
First, we focus on the first term and bound the variation of the truncated squared costs. We claim that, for every i i i and every p , q ∈ R p,q\in R p , q ∈ R ,
∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 ≲ ρ R 2 ℓ ~ i ( p ) + ρ R 4 . \lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2\lesssim\rho_R^2\widetilde{\ell}_i(p)+\rho_R^4. ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2 ≲ ρ R 2 ℓ i ( p ) + ρ R 4 .
If the truncated cost is constant on R R R , then ℓ ~ i ( p ) = ℓ ~ i ( q ) \widetilde{\ell}_i(p)=\widetilde{\ell}_i(q) ℓ i ( p ) = ℓ i ( q ) , and there is nothing to prove. Otherwise, using the triangle inequality, we get
∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ = ∣ d ( p , c i ) 2 − d ( q , c i ) 2 ∣ ≤ d ( p , q ) ( d ( p , c i ) + d ( q , c i ) ) ≤ d ( p , q ) ( 2 d ( p , c i ) + d ( p , q ) ) ≲ ρ R d ( p , c i ) + ρ R 2 , \begin{aligned}
\lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert
&=\lvert d(p,c_i)^2-d(q,c_i)^2\rvert\\
&\le d(p,q)\left(d(p,c_i)+d(q,c_i)\right)\\
&\le d(p,q)\left(2d(p,c_i)+d(p,q)\right)\\
&\lesssim\rho_Rd(p,c_i)+\rho_R^2,
\end{aligned} ∣ ℓ i ( p ) − ℓ i ( q )∣ = ∣ d ( p , c i ) 2 − d ( q , c i ) 2 ∣ ≤ d ( p , q ) ( d ( p , c i ) + d ( q , c i ) ) ≤ d ( p , q ) ( 2 d ( p , c i ) + d ( p , q ) ) ≲ ρ R d ( p , c i ) + ρ R 2 ,
where the last step uses p , q ∈ R p,q\in R p , q ∈ R . Squaring gives
∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 ≲ ρ R 2 d ( p , c i ) 2 + ρ R 4 = ρ R 2 ℓ ~ i ( p ) + ρ R 4 , \lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2\lesssim\rho_R^2d(p,c_i)^2+\rho_R^4=\rho_R^2\widetilde{\ell}_i(p)+\rho_R^4, ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2 ≲ ρ R 2 d ( p , c i ) 2 + ρ R 4 = ρ R 2 ℓ i ( p ) + ρ R 4 ,
as claimed.
We now average the pairwise bound over independent uniform points p , q ∼ R p,q\sim R p , q ∼ R . Using the truncated-cost variation bound, the cost-variation part is at most
E p , q ∼ R ∑ i ( x p , i ⋆ + x q , i ⋆ ) ∣ ℓ ~ i ( p ) − ℓ ~ i ( q ) ∣ 2 \mathbb{E}_{p,q\sim R}\sum_i\left(x_{p,i}^\star+x_{q,i}^\star\right)\lvert\widetilde{\ell}_i(p)-\widetilde{\ell}_i(q)\rvert^2 E p , q ∼ R i ∑ ( x p , i ⋆ + x q , i ⋆ ) ∣ ℓ i ( p ) − ℓ i ( q ) ∣ 2
≲ E p , q ∼ R [ ρ R 2 ∑ i x p , i ⋆ ℓ ~ i ( p ) + ρ R 2 ∑ i x q , i ⋆ ℓ ~ i ( q ) + ρ R 4 ] \lesssim\mathbb{E}_{p,q\sim R}\left[\rho_R^2\sum_i x_{p,i}^\star\widetilde{\ell}_i(p)+\rho_R^2\sum_i x_{q,i}^\star\widetilde{\ell}_i(q)+\rho_R^4\right] ≲ E p , q ∼ R [ ρ R 2 i ∑ x p , i ⋆ ℓ i ( p ) + ρ R 2 i ∑ x q , i ⋆ ℓ i ( q ) + ρ R 4 ]
≲ ρ R 2 n R cost R + ρ R 4 . \lesssim\frac{\rho_R^2}{n_R}\operatorname{cost}_R+\rho_R^4. ≲ n R ρ R 2 cost R + ρ R 4 .
Second, using the definition of G R G_R G R , the second term contributes
E p , q ∼ R ρ R 2 ε ∑ i ( x p , i ⋆ s p , i + x q , i ⋆ s q , i ) \mathbb{E}_{p,q\sim R}\frac{\rho_R^2}{\varepsilon}\sum_i\left(x_{p,i}^\star s_{p,i}+x_{q,i}^\star s_{q,i}\right) E p , q ∼ R ε ρ R 2 i ∑ ( x p , i ⋆ s p , i + x q , i ⋆ s q , i )
≲ ρ R 2 ε n R G R . \lesssim\frac{\rho_R^2}{\varepsilon n_R}G_R. ≲ ε n R ρ R 2 G R .
Therefore,
Var p ∼ R [ g R ( p ) ] ≲ ρ R 2 n R cost ~ R + ρ R 4 + ρ R 2 ε n R G R \operatorname{Var}_{p\sim R}[g_R(p)] \lesssim\frac{\rho_R^2}{n_R}\widetilde{\operatorname{cost}}_R+\rho_R^4+\frac{\rho_R^2}{\varepsilon n_R}\mathcal{G}_R Var p ∼ R [ g R ( p )] ≲ n R ρ R 2 cost R + ρ R 4 + ε n R ρ R 2 G R
Multiplying by n R / ρ R 2 n_R/\rho_R^2 n R / ρ R 2 and summing over rings gives
∑ R n R ρ R 2 Var p ∼ R [ g R ( p ) ] ≲ ∑ R cost ~ R + ∑ R n R ρ R 2 + ε − 1 ∑ R G R = cost ~ p ( C , h ) + W 2 + ε − 1 Δ C , h ( β ) \begin{aligned}
\sum_R\frac{n_R}{\rho_R^2}\operatorname{Var}_{p\sim R}[g_R(p)]\lesssim\sum_R\widetilde{\operatorname{cost}}_R+\sum_R n_R\rho_R^2+\varepsilon^{-1}\sum_R\mathcal{G}_R \\
&=\widetilde{\operatorname{cost}}_p(C,h)+W_2+\varepsilon^{-1}\Delta_{C,h}(\beta)
\end{aligned} R ∑ ρ R 2 n R Var p ∼ R [ g R ( p )] ≲ R ∑ cost R + R ∑ n R ρ R 2 + ε − 1 R ∑ G R = cost p ( C , h ) + W 2 + ε − 1 Δ C , h ( β )
≲ cost ~ p ( C , h ) + ε − 1 Δ C , h ( β ) \lesssim\widetilde{\operatorname{cost}}_p(C,h)+\varepsilon^{-1}\Delta_{C,h}(\beta) ≲ cost p ( C , h ) + ε − 1 Δ C , h ( β )
as required.
Proof of the dual-vector discretization lemma
We prove Lemma 5.9 . Fix C ∈ X k C\in X^k C ∈ X k , and let D \mathcal{D} D be the set of points lying in rings. Choose a constant K ≲ ε − 1 K\lesssim\varepsilon^{-1} K ≲ ε − 1 such that the centered range bound gives
∣ f C , β ( p ) − f C , β ( a R ) ∣ ≤ K ρ R 2 \left|f_{C,\beta}(p)-f_{C,\beta}(a_R)\right|\le K\rho_R^2 ∣ f C , β ( p ) − f C , β ( a R ) ∣ ≤ K ρ R 2
for every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k and every p ∈ R p\in R p ∈ R .
For p ∈ D p\in\mathcal{D} p ∈ D , where R R R is the ring containing p p p , define the normalized residual directly by
G C , β ( p ) = f C , β ( p ) − f C , β ( a R ) K ρ R 2 . G_{C,\beta}(p)=\frac{f_{C,\beta}(p)-f_{C,\beta}(a_R)}{K\rho_R^2}. G C , β ( p ) = K ρ R 2 f C , β ( p ) − f C , β ( a R ) .
Thus G C , β ∈ [ − 1 , 1 ] D G_{C,\beta}\in[-1,1]^{\mathcal{D}} G C , β ∈ [ − 1 , 1 ] D .
We use the following residual-net bound.
Lemma 5.11 (Residual net for fixed centers). Fix C ∈ X k C\in X^k C ∈ X k . For every γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) , the class
G C = { G C , β : β ∈ R k } \mathcal{G}_C=\{G_{C,\beta}:\beta\in\mathbb{R}^k\} G C = { G C , β : β ∈ R k } has a γ \gamma γ -net in ℓ ∞ ( D ) \ell_\infty(\mathcal{D}) ℓ ∞ ( D ) of size at most
( N k 2 γ ) O ( k ) . \left(\frac{Nk^2}{\gamma}\right)^{O(k)}. ( γ N k 2 ) O ( k ) .
The lemma follows by an almost identical argument as in the proof of Lemma 4.6 . Instead of working with d ( p , c ) d(p,c) d ( p , c ) , we have truncated costs ℓ ~ i \tilde{\ell}_i ℓ ~ i . For fixed C C C , the minimizer pattern is still determined by an arrangement of O ( N k 2 ) O(Nk^2) O ( N k 2 ) hyperplanes in β \beta β -space, and on each cell the residual vector G C , β G_{C,\beta} G C , β is affine in β \beta β . Since the centered-range bound gives G C , β ∈ [ − 1 , 1 ] D G_{C,\beta}\in[-1,1]^{\mathcal{D}} G C , β ∈ [ − 1 , 1 ] D , the same volumetric covering argument gives the claimed net size.
The discretization argument also uses two deterministic bounds due to the ring decomposition. First, the allowed error A C ( β ) A_C(\beta) A C ( β ) is never smaller than ε W 2 \varepsilon W_2 ε W 2 . Second, the total sampling error is always bounded by the maximum centered range on the rings.
The next lemma records two deterministic bounds that set the relevant scale for the discretization: the allowed error is always at least the ring scale, and the sampling error is always at most the total centered range over the rings.
Lemma 5.12 (Deterministic bound). For every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k ,
A C ( β ) ≳ ε W 2 A_C(\beta)\gtrsim\varepsilon W_2 A C ( β ) ≳ ε W 2 and
∣ Err C ( β ) ∣ ≲ ε − 1 W 2 . \left|\operatorname{Err}_C(\beta)\right|\lesssim\varepsilon^{-1}W_2. ∣ Err C ( β ) ∣ ≲ ε − 1 W 2 .
Proof. For every feasible demand vector h h h , the ring construction and the truncation comparison imply
W 2 ≲ OPT ≤ cost P ( C , h ) ≲ cost ~ P ( C , h ) . W_2 \lesssim\operatorname{OPT} \leq\operatorname{cost}_P(C,h) \lesssim\widetilde{\operatorname{cost}}_P(C,h). W 2 ≲ OPT ≤ cost P ( C , h ) ≲ cost P ( C , h ) .
Since dual gaps are nonnegative,
A C ( β ) = inf h ∈ n Δ k ( ε cost ~ P ( C , h ) + 1 4 Δ C , h ( β ) ) ≳ ε W 2 . A_C(\beta)=\inf_{h\in n\Delta_k}\left(\varepsilon\widetilde{\operatorname{cost}}_P(C,h)+\frac{1}{4}\Delta_{C,h}(\beta)\right)\gtrsim\varepsilon W_2. A C ( β ) = h ∈ n Δ k inf ( ε cost P ( C , h ) + 4 1 Δ C , h ( β ) ) ≳ ε W 2 .
For the error bound, we write the sampling error in centered form. Since the sampled points from ring R R R have total weight exactly n R n_R n R , the anchor value f C , β ( a R ) f_{C,\beta}(a_R) f C , β ( a R ) cancels, and
Err C ( β ) = ∑ R n R ( 1 m R ∑ q ∈ Q R ( f C , β ( q ) − f C , β ( a R ) ) − 1 n R ∑ p ∈ R ( f C , β ( p ) − f C , β ( a R ) ) ) . \operatorname{Err}_C(\beta)=\sum_R n_R\left(\frac{1}{m_R}\sum_{q\in Q_R}\left(f_{C,\beta}(q)-f_{C,\beta}(a_R)\right)-\frac{1}{n_R}\sum_{p\in R}\left(f_{C,\beta}(p)-f_{C,\beta}(a_R)\right)\right). Err C ( β ) = R ∑ n R m R 1 q ∈ Q R ∑ ( f C , β ( q ) − f C , β ( a R ) ) − n R 1 p ∈ R ∑ ( f C , β ( p ) − f C , β ( a R ) ) .
By the centered range bound, every term inside the averages for ring R R R has magnitude at most O ( ε − 1 ρ R 2 ) O(\varepsilon^{-1}\rho_R^2) O ( ε − 1 ρ R 2 ) . Hence the two averages differ by at most O ( ε − 1 ρ R 2 ) O(\varepsilon^{-1}\rho_R^2) O ( ε − 1 ρ R 2 ) , and therefore
∣ Err C ( β ) ∣ ≲ ∑ R n R ε − 1 ρ R 2 = ε − 1 W 2 . \left|\operatorname{Err}_C(\beta)\right|\lesssim\sum_R n_R\varepsilon^{-1}\rho_R^2=\varepsilon^{-1}W_2. ∣ Err C ( β ) ∣ ≲ R ∑ n R ε − 1 ρ R 2 = ε − 1 W 2 .
Proof of Lemma 5.9 . By Lemma 5.12 , every dual vector satisfies A C ( β ) ≳ ε W 2 A_C(\beta)\gtrsim\varepsilon W_2 A C ( β ) ≳ ε W 2 and ∣ Err C ( β ) ∣ ≲ ε − 1 W 2 \left|\operatorname{Err}_C(\beta)\right|\lesssim\varepsilon^{-1}W_2 ∣ Err C ( β ) ∣ ≲ ε − 1 W 2 . It remains to consider the range
ε W 2 ≲ A C ( β ) ≲ ε − 1 W 2 . \varepsilon W_2\lesssim A_C(\beta)\lesssim\varepsilon^{-1}W_2. ε W 2 ≲ A C ( β ) ≲ ε − 1 W 2 .
Indeed, if A C ( β ) A_C(\beta) A C ( β ) is larger than a sufficiently large constant multiple of ε − 1 W 2 \varepsilon^{-1}W_2 ε − 1 W 2 , then the bound ∣ Err C ( β ) ∣ ≲ ε − 1 W 2 \left|\operatorname{Err}_C(\beta)\right|\lesssim\varepsilon^{-1}W_2 ∣ Err C ( β ) ∣ ≲ ε − 1 W 2 already implies ∣ Err C ( β ) ∣ ≤ A C ( β ) \left|\operatorname{Err}_C(\beta)\right|\leq A_C(\beta) ∣ Err C ( β ) ∣ ≤ A C ( β ) .
Let
λ 0 = c ε W 2 , λ j = 2 j λ 0 , \lambda_0=c\varepsilon W_2,\qquad\lambda_j=2^j\lambda_0, λ 0 = c ε W 2 , λ j = 2 j λ 0 ,
and define the shells
S j = { β ∈ R k : λ j ≤ A C ( β ) < 2 λ j } . S_j=\{\beta\in\mathbb{R}^k:\lambda_j\leq A_C(\beta)<2\lambda_j\}. S j = { β ∈ R k : λ j ≤ A C ( β ) < 2 λ j } .
Only O ( log ( 1 / ε ) ) O(\log(1/\varepsilon)) O ( log ( 1/ ε )) shells can intersect the relevant range above.
For each nonempty shell S j S_j S j , take a net for { G C , β : β ∈ S j } \{G_{C,\beta}:\beta\in S_j\} { G C , β : β ∈ S j } in the metric ℓ ∞ ( D ) \ell_\infty(\mathcal{D}) ℓ ∞ ( D ) at resolution
γ = c 0 ε , \gamma=c_0\varepsilon, γ = c 0 ε ,
where c 0 > 0 c_0>0 c 0 > 0 is a sufficiently small universal constant. By Lemma 5.11 , each shell has a net of size at most
( N k ε ) O ( k ) . \left(\frac{Nk}{\varepsilon}\right)^{O(k)}. ( ε N k ) O ( k ) .
Taking the union over all relevant shells gives a representative set B C \mathcal{B}_C B C satisfying
∣ B C ∣ ≤ exp { O ( k log ( N / ε ) ) } . |\mathcal{B}_C|\leq\exp\{O(k\log(N/\varepsilon))\}. ∣ B C ∣ ≤ exp { O ( k log ( N / ε ))} .
Conditioning on the event that every representative β ′ ∈ B C \beta'\in\mathcal{B}_C β ′ ∈ B C satisfies ∣ Err C ( β ′ ) ∣ ≤ 1 8 A C ( β ′ ) \left|\operatorname{Err}_C(\beta')\right|\leq\frac{1}{8}A_C(\beta') ∣ Err C ( β ′ ) ∣ ≤ 8 1 A C ( β ′ ) , we show that the same type of bound holds for every β ∈ R k \beta\in\mathbb{R}^k β ∈ R k in the relevant range. Fix such a β \beta β , and let j j j be such that β ∈ S j \beta\in S_j β ∈ S j . Choose β ′ ∈ B C ∩ S j \beta'\in\mathcal{B}_C\cap S_j β ′ ∈ B C ∩ S j such that
∥ G C , β − G C , β ′ ∥ ∞ ≤ γ . \left\|G_{C,\beta}-G_{C,\beta'}\right\|_\infty\leq\gamma. ∥ G C , β − G C , β ′ ∥ ∞ ≤ γ .
Since β ′ ∈ S j \beta' \in S_j β ′ ∈ S j , we have
A C ( β ′ ) < 2 λ j , A_C(\beta') < 2\lambda_j, A C ( β ′ ) < 2 λ j ,
and therefore
∣ Err C ( β ′ ) ∣ ≤ 1 8 A C ( β ′ ) < 1 4 λ j . |\operatorname{Err}_C(\beta')| \le\frac{1}{8}A_C(\beta') < \frac{1}{4}\lambda_j. ∣ Err C ( β ′ ) ∣ ≤ 8 1 A C ( β ′ ) < 4 1 λ j .
It remains to compare the errors of β \beta β and β ′ \beta' β ′ . Using the centered form of the sampling error, the anchor terms cancel ring by ring. By the definition of G C , β G_{C,\beta} G C , β ,
∣ Err C ( β ) − Err C ( β ′ ) ∣ ≲ ε − 1 W 2 ∥ G C , β − G C , β ′ ∥ ∞ ≤ ε − 1 W 2 γ = c 0 ε W 2 . \begin{aligned}
|\operatorname{Err}_C(\beta)-\operatorname{Err}_C(\beta')| &\lesssim\varepsilon^{-1}W_2\|G_{C,\beta}-G_{C,\beta'}\|_\infty\\
&\le\varepsilon^{-1}W_2\gamma\\
&=c_0\varepsilon W_2.
\end{aligned} ∣ Err C ( β ) − Err C ( β ′ ) ∣ ≲ ε − 1 W 2 ∥ G C , β − G C , β ′ ∥ ∞ ≤ ε − 1 W 2 γ = c 0 ε W 2 .
By the lower bound on the allowed error, A C ( β ) ≳ ε W 2 A_C(\beta)\gtrsim\varepsilon W_2 A C ( β ) ≳ ε W 2 . Since β ∈ S j \beta\in S_j β ∈ S j , this also means λ j ≳ ε W 2 \lambda_j\gtrsim\varepsilon W_2 λ j ≳ ε W 2 . Choosing c 0 c_0 c 0 sufficiently small, we get
∣ Err C ( β ) − Err C ( β ′ ) ∣ ≤ 1 4 λ j . |\operatorname{Err}_C(\beta)-\operatorname{Err}_C(\beta')|\le\frac{1}{4}\lambda_j. ∣ Err C ( β ) − Err C ( β ′ ) ∣ ≤ 4 1 λ j .
Combining the two estimates,
∣ Err C ( β ) ∣ ≤ ∣ Err C ( β ′ ) ∣ + ∣ Err C ( β ) − Err C ( β ′ ) ∣ < 1 2 λ j ≤ A C ( β ) . |\operatorname{Err}_C(\beta)|\le|\operatorname{Err}_C(\beta')|+|\operatorname{Err}_C(\beta)-\operatorname{Err}_C(\beta')|<\frac{1}{2}\lambda_j\le A_C(\beta). ∣ Err C ( β ) ∣ ≤ ∣ Err C ( β ′ ) ∣ + ∣ Err C ( β ) − Err C ( β ′ ) ∣ < 2 1 λ j ≤ A C ( β ) .
This proves Lemma 5.9.
Euclidean Capacitated k k k -median
We next prove the Euclidean coreset theorem for capacitated k k k -median. Note that, in this section, we reuse the variable d d d to denote the dimension of the Euclidean space the points lie in.
Theorem 6.1 (Euclidean capacitated k k k -median). Let P ⊆ R d P\subseteq\mathbb{R}^d P ⊆ R d be a set of n n n points. For every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , there is an algorithm which outputs a weighted subset Q ⊆ P Q\subseteq P Q ⊆ P of size
∣ Q ∣ = O ~ ( k ε − 4 + k ε − 2 log ( 1 / δ ) ) . |Q|=\widetilde{O}\left(k\varepsilon^{-4}+k\varepsilon^{-2}\log(1/\delta)\right). ∣ Q ∣ = O ( k ε − 4 + k ε − 2 log ( 1/ δ ) ) . such that, with probability at least 1 − δ 1-\delta 1 − δ , Q Q Q is an ε \varepsilon ε -coreset for Euclidean capacitated k k k -median.
We will in fact show the following dimension-dependent coreset bound.
Lemma 6.2 (Dimension-dependent coreset). There is an algorithm which, with probability at least 1 − δ 1-\delta 1 − δ , outputs an ε \varepsilon ε -coreset Q ⊆ P Q\subseteq P Q ⊆ P for Euclidean capacitated k k k -median of size
O ~ ( k d ε − 2 + k ε − 2 log ( 1 / δ ) ) . \widetilde{O}\left(kd\varepsilon^{-2}+k\varepsilon^{-2}\log(1/\delta)\right). O ( k d ε − 2 + k ε − 2 log ( 1/ δ ) ) .
Once Lemma 6.2 is proved, Theorem 6.1 follows via the ideas of terminal embeddings and the existence of poly ( k / ε ) \operatorname{poly}(k/\varepsilon) poly ( k / ε ) -size coresets for Euclidean k k k -median. This reduction is standard, so we defer the details to Section C.2.
Mass-Preserving Sensitivity Sampling
We set up some basic notation required to state the algorithm.
Let A = { a 1 , … , a k } ⊆ R d A = \{a_1,\ldots,a_k\} \subseteq\mathbb{R}^d A = { a 1 , … , a k } ⊆ R d be a constant-factor approximate unconstrained k k k -median solution for P P P . For j ∈ [ k ] j \in[k] j ∈ [ k ] , let P j P_j P j be the set of points in P P P whose nearest anchor in A A A is a j a_j a j with ties being broken arbitrarily. For each p ∈ P j p \in P_j p ∈ P j , define r p = ∥ p − a j ∥ r_p = \lVert p-a_j\rVert r p = ∥ p − a j ∥ and let
Φ j = ∑ p ∈ P j r p , W 1 = ∑ j ∈ [ k ] Φ j ≲ O P T , \Phi_j = \sum_{p \in P_j} r_p,\qquad W_1 = \sum_{j \in[k]} \Phi_j \lesssim\mathrm{OPT}, Φ j = p ∈ P j ∑ r p , W 1 = j ∈ [ k ] ∑ Φ j ≲ OPT ,
where OPT denotes the optimum unconstrained Euclidean k k k -median cost of P P P .
Algorithm. For each cluster P j P_j P j , the algorithm samples m j m_j m j points from it where m j m_j m j is chosen proportional to the cost Φ j \Phi_j Φ j of the cluster. Within P j P_j P j , the samples are drawn i.i.d. from a distribution π j \pi_j π j which is a mixture of the uniform distribution and the distribution proportional to r p r_p r p . Sampling uniformly ensures that the mass of the distribution is preserved up to a ( 1 ± ε ) (1 \pm\varepsilon) ( 1 ± ε ) factor and sampling high-cost points with larger probability ensures that the variance of the estimator is low. After sampling, the weights of points within the cluster are rescaled so that the total weight of the samples from cluster P j P_j P j is exactly ∣ P j ∣ \lvert P_j\rvert ∣ P j ∣ .
Throughout we assume that each cluster P j P_j P j has cost Φ j > 0 \Phi_j > 0 Φ j > 0 . This is without loss of generality: if a cluster has a cost 0 0 0 , then it can be represented by a single point with weight equal to the size of the cluster. This increases the coreset size by at most k k k .
Algorithm 2 Mass-preserving sensitivity sampling for Euclidean capacitated k k k -median
Compute the O ( 1 ) O(1) O ( 1 ) -approximate solution A A A and the clusters P 1 , … , P k P_1,\ldots,P_k P 1 , … , P k induced by A A A .
Let T = Θ ~ ( k ε − 2 ( d + log ( 1 / δ ) ) ) T = \widetilde{\Theta}(k\varepsilon^{-2}(d+\log(1/\delta))) T = Θ ( k ε − 2 ( d + log ( 1/ δ ))) and m 0 = Θ ( ε − 2 log ( k / δ ) ) m_0 = \Theta(\varepsilon^{-2}\log(k/\delta)) m 0 = Θ ( ε − 2 log ( k / δ )) .
for each cluster P j P_j P j do
Set m j = ⌈ T Φ j / W 1 ⌉ + m 0 m_j = \lceil T\Phi_j/W_1\rceil+ m_0 m j = ⌈ T Φ j / W 1 ⌉ + m 0 . Sample a multiset Q j Q_j Q j of m j m_j m j points i.i.d. from the distribution
π j ( p ) = 1 2 ( 1 ∣ P j ∣ + r p Φ j ) , p ∈ P j . \pi_j(p) = \frac{1}{2}\left(\frac{1}{\lvert P_j\rvert}+\frac{r_p}{\Phi_j}\right),\qquad p \in P_j. π j ( p ) = 2 1 ( ∣ P j ∣ 1 + Φ j r p ) , p ∈ P j .
Assign each occurrence q ∈ Q j q \in Q_j q ∈ Q j the initial weight w ~ q = ( m j π j ( q ) ) − 1 \widetilde{w}_q = (m_j\pi_j(q))^{-1} w q = ( m j π j ( q ) ) − 1 .
Let λ j = ∣ P j ∣ / ( ∑ q ∈ Q j w ~ q ) \lambda_j = \lvert P_j\rvert/\left(\sum_{q \in Q_j}\widetilde{w}_q\right) λ j = ∣ P j ∣ / ( ∑ q ∈ Q j w q ) .
Rescale the weights, setting w q = λ j w ~ q w_q = \lambda_j\widetilde{w}_q w q = λ j w q for every q ∈ Q j q \in Q_j q ∈ Q j , so that ∑ q ∈ Q j w q = ∣ P j ∣ \sum_{q \in Q_j}w_q = \lvert P_j\rvert ∑ q ∈ Q j w q = ∣ P j ∣ .
end for
Output: the resulting weighted multiset Q = ⋃ j = 1 k Q j Q = \bigcup_{j=1}^k Q_j Q = ⋃ j = 1 k Q j .
We note some simple properties of the algorithm that will be used in the analysis.
Claim 6.3 (Cluster Mass Preservation). The following properties hold.
(i) (Initial Weights ) With probability at least 1 − δ 1-\delta 1 − δ , for all j ∈ [ k ] j \in[k] j ∈ [ k ] , we have ∑ q ∈ Q j w ~ q = ( 1 ± ε ) ∣ P j ∣ \sum_{q \in Q_j}\widetilde{w}_q = (1\pm\varepsilon)\lvert P_j\rvert ∑ q ∈ Q j w q = ( 1 ± ε ) ∣ P j ∣ .
(ii) (Final Weights ) With probability 1 1 1 , for all j ∈ [ k ] j \in[k] j ∈ [ k ] , we have ∑ q ∈ Q j w q = ∣ P j ∣ \sum_{q \in Q_j}w_q = \lvert P_j\rvert ∑ q ∈ Q j w q = ∣ P j ∣ .
(iii) If the event in (i) occurs, then for all q ∈ Q q \in Q q ∈ Q we have ∣ w q − w ~ q ∣ ≲ ε w ~ q \lvert w_q-\widetilde{w}_q\rvert\lesssim\varepsilon\widetilde{w}_q ∣ w q − w q ∣ ≲ ε w q .
Proof. (i) Fix j ∈ [ k ] j \in[k] j ∈ [ k ] , and write M ^ j = ∑ q ∈ Q j w ^ q \widehat{M}_j = \sum_{q \in Q_j} \widehat{w}_q M j = ∑ q ∈ Q j w q . Each sampled occurrence has expected initial weight ∣ P j ∣ / m j |P_j|/m_j ∣ P j ∣/ m j , so E [ M ^ j ] = ∣ P j ∣ \mathbb{E}[\widehat{M}_j] = |P_j| E [ M j ] = ∣ P j ∣ . Moreover, since π j ( p ) ≥ 1 / ( 2 ∣ P j ∣ ) \pi_j(p) \ge1/(2|P_j|) π j ( p ) ≥ 1/ ( 2∣ P j ∣ ) , every initial weight is at most 2 ∣ P j ∣ / m j 2|P_j|/m_j 2∣ P j ∣/ m j . Hence Hoeffding’s inequality (see B.1) gives
Pr [ ∣ M ^ j − ∣ P j ∣ ∣ > ε ∣ P j ∣ ] ≤ 2 exp ( − Ω ( ε 2 m j ) ) ≤ δ / k . \Pr\left[|\widehat{M}_j - |P_j|| > \varepsilon|P_j|\right] \le2\exp\left(-\Omega(\varepsilon^2m_j)\right) \le\delta/k. Pr [ ∣ M j − ∣ P j ∣∣ > ε ∣ P j ∣ ] ≤ 2 exp ( − Ω ( ε 2 m j ) ) ≤ δ / k .
where we used m j ≥ m 0 = Θ ( ε − 2 log ( k / δ ) ) m_j \ge m_0 = \Theta(\varepsilon^{-2}\log(k/\delta)) m j ≥ m 0 = Θ ( ε − 2 log ( k / δ )) . A union bound over j ∈ [ k ] j \in[k] j ∈ [ k ] proves (i).
(ii) This follows immediately from the rescaling step of the algorithm.
(iii) It follows from (i), (ii) that the rescaling factor λ j = 1 ± O ( ε ) \lambda_j = 1 \pm O(\varepsilon) λ j = 1 ± O ( ε ) , which implies (iii).
Analysis
Our main goal is to prove Lemma 6.2 . We follow the same dual-based approach used in § 4 for finite-metric k k k -median. The quantities f C , β f_{C,\beta} f C , β , DualS ( C , h , β ) \operatorname{DualS}(C,h,\beta) DualS ( C , h , β ) , and Err C ( β ) \operatorname{Err}_C(\beta) Err C ( β ) are used with the same meaning as before, with Euclidean distance replacing the finite metric.
The following lemma is the same dual-to-primal step proved in the finite-metric section.
Lemma 6.4 (Dual preservation implies load preservation). For every fixed C ∈ ( R d ) k C \in(\mathbb{R}^d)^k C ∈ ( R d ) k , if
sup β ∈ R k ∣ Err C ( β ) ∣ ≤ η , then sup h ∈ n Δ k ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η . (14) \sup_{\beta\in\mathbb{R}^k} |\operatorname{Err}_C(\beta)| \le\eta,\qquad\text{then}\qquad\sup_{h \in n\Delta_k} |\operatorname{cost}_Q(C,h) - \operatorname{cost}_P(C,h)| \le\eta. \tag*{(14)} β ∈ R k sup ∣ Err C ( β ) ∣ ≤ η , then h ∈ n Δ k sup ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≤ η . (14)
We next center the dual functions f C , β f_{C,\beta} f C , β at the anchors. For each point p p p that is in cluster P j P_j P j
g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) . (15) g_{C,\beta}(p) = f_{C,\beta}(p) - f_{C,\beta}(a_j). \tag*{(15)} g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) . (15)
Since f C , β f_{C,\beta} f C , β is 1-Lipschitz for k k k -median,
∣ g C , β ( p ) ∣ ≤ ∥ p − a j ∥ = r p . (16) |g_{C,\beta}(p)| \le\lVert p-a_j\rVert= r_p. \tag*{(16)} ∣ g C , β ( p ) ∣ ≤ ∥ p − a j ∥ = r p . (16)
Furthermore, we can express the dual error in terms of g C , β g_{C,\beta} g C , β . Here we crucially use that the algorithm preserves the mass of each cluster.
Claim 6.5. For every C C C and β \beta β ,
Err C ( β ) = ∑ q ∈ Q w q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) . \operatorname{Err}_C(\beta) = \sum_{q \in Q} w_q g_{C,\beta}(q) - \sum_{p \in P} g_{C,\beta}(p). Err C ( β ) = q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) .
Proof. Fix j ∈ [ k ] j \in[k] j ∈ [ k ] . Since f C , β ( p ) = g C , β ( p ) + f C , β ( a j ) f_{C,\beta}(p) = g_{C,\beta}(p) + f_{C,\beta}(a_j) f C , β ( p ) = g C , β ( p ) + f C , β ( a j ) for a point p ∈ P j p \in P_j p ∈ P j ,
∑ q ∈ Q j w q f C , β ( q ) − ∑ p ∈ P j f C , β ( p ) = ∑ q ∈ Q j w q g C , β ( q ) − ∑ p ∈ P j g C , β ( p ) + f C , β ( a j ) ( ∑ q ∈ Q j w q − ∣ P j ∣ ) = ∑ q ∈ Q j w q g C , β ( q ) − ∑ p ∈ P j g C , β ( p ) . \begin{aligned}
\sum_{q \in Q_j} w_q f_{C,\beta}(q) - \sum_{p \in P_j} f_{C,\beta}(p)
&= \sum_{q \in Q_j} w_q g_{C,\beta}(q) - \sum_{p \in P_j} g_{C,\beta}(p) + f_{C,\beta}(a_j)\left(\sum_{q \in Q_j} w_q - |P_j|\right) \\
&= \sum_{q \in Q_j} w_q g_{C,\beta}(q) - \sum_{p \in P_j} g_{C,\beta}(p).
\end{aligned} q ∈ Q j ∑ w q f C , β ( q ) − p ∈ P j ∑ f C , β ( p ) = q ∈ Q j ∑ w q g C , β ( q ) − p ∈ P j ∑ g C , β ( p ) + f C , β ( a j ) q ∈ Q j ∑ w q − ∣ P j ∣ = q ∈ Q j ∑ w q g C , β ( q ) − p ∈ P j ∑ g C , β ( p ) .
The last term is zero by property (ii) of Claim 6.3 . Summing over j ∈ [ k ] j \in[k] j ∈ [ k ] proves the claim.
Due to the rescaling of weights that the algorithm does, the right-hand side of the identity in Claim 6.5 , which involves the final weights w q w_q w q , is not a sum of independent random variables. In order to be able to apply concentration inequalities, we decompose the error into terms as follows and bound each of them separately.
∣ Err C ( β ) ∣ ≤ ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ + ∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ . (17) |\operatorname{Err}_C(\beta)| \le\left|\sum_{q \in Q} \widehat{w}_q g_{C,\beta}(q) - \sum_{p \in P} g_{C,\beta}(p)\right| + \left|\sum_{q \in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|. \tag*{(17)} ∣ Err C ( β ) ∣ ≤ q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) + q ∈ Q ∑ ( w q − w q ) g C , β ( q ) . (17)
Lemma 6.6 (Error before rescaling). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ ε W 1 . \sup_{C,\beta}\left|\sum_{q\in Q}\widehat{w}_q g_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right|\lesssim\varepsilon W_1. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ ε W 1 .
Lemma 6.7 (Rescaling error). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε W 1 . \sup_{C,\beta}\left|\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon W_1. C , β sup q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε W 1 .
We now show that the above lemmas complete the proof of the coreset bound.
Proof of Lemma 6.2. By Lemma 6.6, Lemma 6.7, and (17) , with probability at least 1 − δ 1-\delta 1 − δ ,
sup C , β ∣ Err C ( β ) ∣ ≲ ε W 1 . \sup_{C,\beta}|\operatorname{Err}_{C}(\beta)|\lesssim\varepsilon W_1. C , β sup ∣ Err C ( β ) ∣ ≲ ε W 1 .
Thus, by Lemma 6.4 , for every C ∈ ( R d ) k C\in(\mathbb{R}^{d})^{k} C ∈ ( R d ) k and h ∈ n Δ k h\in n\Delta_{k} h ∈ n Δ k ,
∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≲ ε W 1 ≲ ε OPT ≲ ε cost P ( C , h ) . |\operatorname{cost}_{Q}(C,h)-\operatorname{cost}_{P}(C,h)|\lesssim\varepsilon W_1\lesssim\varepsilon\operatorname{OPT}\lesssim\varepsilon\operatorname{cost}_{P}(C,h). ∣ cost Q ( C , h ) − cost P ( C , h ) ∣ ≲ ε W 1 ≲ ε OPT ≲ ε cost P ( C , h ) .
The bound on the coreset size follows from the choice of m j m_j m j :
∑ j ∈ [ k ] m j ≤ T + k + k m 0 = O ~ ( k d ε − 2 + k ε − 2 log ( 1 / δ ) ) . \sum_{j\in[k]}m_j\le T+k+km_0=\widetilde{O}\left(kd\varepsilon^{-2}+k\varepsilon^{-2}\log(1/\delta)\right). j ∈ [ k ] ∑ m j ≤ T + k + k m 0 = O ( k d ε − 2 + k ε − 2 log ( 1/ δ ) ) .
The rest of this section is devoted to proving Lemma 6.6 and Lemma 6.7.
Bounding the Error Before Rescaling Via Pseudo-Dimension: Proof of Lemma 6.6
We prove Lemma 6.6 using the pseudo-dimension tools collected in Section B.1. The argument is to normalize the sampled summands, bound the pseudo-dimension of the resulting function class, and then apply uniform convergence.
For each set of centers C C C and dual vector β \beta β , define
F C , β ( p ) = T 2 W 1 w ^ p g C , β ( p ) . (18) F_{C,\beta}(p)=\frac{T}{2W_1}\widehat{w}_p g_{C,\beta}(p). \tag*{(18)} F C , β ( p ) = 2 W 1 T w p g C , β ( p ) . (18)
In the above equation, for a point p p p in cluster P j P_j P j we use w ^ p = 1 / ( m j π j ( p ) ) \widehat{w}_p=1/(m_j\pi_j(p)) w p = 1/ ( m j π j ( p )) . This is the initial weight assigned if p p p is sampled by Algorithm 2. The point of defining F F F is that we can express the error before weight rescaling in terms of F F F :
∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) = 2 W 1 T ( ∑ q ∈ Q F C , β ( q ) − ∑ q ∈ Q E F C , β ( q ) ) . (19) \sum_{q\in Q}\widehat{w}_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)=\frac{2W_1}{T}\left(\sum_{q\in Q}F_{C,\beta}(q)-\sum_{q\in Q}\mathbb{E}F_{C,\beta}(q)\right). \tag*{(19)} q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) = T 2 W 1 q ∈ Q ∑ F C , β ( q ) − q ∈ Q ∑ E F C , β ( q ) . (19)
The normalization factor T / ( 2 W 1 ) T/(2W_1) T / ( 2 W 1 ) in (18) is chosen so that F C , β F_{C,\beta} F C , β is bounded by 1, as shown below.
Claim 6.8. For every C , β C,\beta C , β , and every p ∈ P p\in P p ∈ P , ∣ F C , β ( p ) ∣ ≤ 1 |F_{C,\beta}(p)|\le1 ∣ F C , β ( p ) ∣ ≤ 1 . Proof. Let p ∈ P j p \in P_j p ∈ P j . If r p = 0 r_p = 0 r p = 0 , then g C , β ( p ) = 0 g_{C,\beta}(p) = 0 g C , β ( p ) = 0 , so the claim is immediate. Otherwise, ∣ g C , β ( p ) ∣ ≤ r p |g_{C,\beta}(p)| \le r_p ∣ g C , β ( p ) ∣ ≤ r p , π j ( p ) ≥ r p / ( 2 Φ j ) \pi_j(p) \ge r_p/(2\Phi_j) π j ( p ) ≥ r p / ( 2 Φ j ) , and m j ≥ T Φ j / W 1 m_j \ge T\Phi_j/W_1 m j ≥ T Φ j / W 1 . Hence
∣ F C , β ( p ) ∣ = T 2 W 1 ∣ g C , β ( p ) ∣ m j π j ( p ) ≤ 1. |F_{C,\beta}(p)| = \frac{T}{2W_1}\frac{|g_{C,\beta}(p)|}{m_j\pi_j(p)} \le1. ∣ F C , β ( p ) ∣ = 2 W 1 T m j π j ( p ) ∣ g C , β ( p ) ∣ ≤ 1.
We now bound the pseudo-dimension of the following function class:
F = { F C , β : C ∈ ( R d ) k , β ∈ R k } . (20) \mathcal{F} = \{F_{C,\beta} : C \in(\mathbb{R}^d)^k,\ \beta\in\mathbb{R}^k\}. \tag*{(20)} F = { F C , β : C ∈ ( R d ) k , β ∈ R k } . (20)
Lemma 6.9. pdim ( F ) = O ~ ( k d ) \operatorname{pdim}(\mathcal{F}) = \widetilde{O}(kd) pdim ( F ) = O ( k d ) .
Proof. Fix points p 1 , … , p m ∈ P p_1,\ldots,p_m \in P p 1 , … , p m ∈ P and thresholds τ 1 , … , τ m ∈ R \tau_1,\ldots,\tau_m \in\mathbb{R} τ 1 , … , τ m ∈ R . We bound the number of possible sign patterns of F C , β ( p ℓ ) − τ ℓ F_{C,\beta}(p_\ell)-\tau_\ell F C , β ( p ℓ ) − τ ℓ as C C C and β \beta β vary.
For p ℓ ∈ P j ℓ p_\ell\in P_{j_\ell} p ℓ ∈ P j ℓ , set
α ℓ = T 2 W 1 w ^ p ℓ > 0. \alpha_\ell= \frac{T}{2W_1}\widehat{w}_{p_\ell} > 0. α ℓ = 2 W 1 T w p ℓ > 0. Then F C , β ( p ℓ ) ≥ τ ℓ F_{C,\beta}(p_\ell) \ge\tau_\ell F C , β ( p ℓ ) ≥ τ ℓ is equivalent to
f C , β ( p ℓ ) − f C , β ( a j ℓ ) ≥ τ ℓ / α ℓ . (21) f_{C,\beta}(p_\ell)-f_{C,\beta}(a_{j_\ell}) \ge\tau_\ell/\alpha_\ell. \tag*{(21)} f C , β ( p ℓ ) − f C , β ( a j ℓ ) ≥ τ ℓ / α ℓ . (21) Recall that f C , β ( x ) = min t ∈ [ k ] { ∥ x − c t ∥ + β t } f_{C,\beta}(x) = \min_{t\in[k]}\{\lVert x-c_t\rVert+\beta_t\} f C , β ( x ) = min t ∈ [ k ] {∥ x − c t ∥ + β t } . Thus each threshold sign is determined by the minimizers defining f C , β ( p ℓ ) f_{C,\beta}(p_\ell) f C , β ( p ℓ ) and f C , β ( a j ℓ ) f_{C,\beta}(a_{j_\ell}) f C , β ( a j ℓ ) , together with one comparison between the corresponding chosen values.
All relevant comparisons that arise have the form
∥ x − c s ∥ + β s ≤ ∥ y − c t ∥ + β t + θ , (22) \lVert x-c_s\rVert+\beta_s \le\lVert y-c_t\rVert+\beta_t+\theta, \tag*{(22)} ∥ x − c s ∥ + β s ≤ ∥ y − c t ∥ + β t + θ , (22) where x , y , θ x,y,\theta x , y , θ are fixed. Writing A = β t + θ − β s A=\beta_t+\theta-\beta_s A = β t + θ − β s , u = ∥ x − c s ∥ 2 u=\lVert x-c_s\rVert^2 u = ∥ x − c s ∥ 2 , and v = ∥ y − c t ∥ 2 v=\lVert y-c_t\rVert^2 v = ∥ y − c t ∥ 2 , the comparison in (22) is u ≤ v + A \sqrt{u}\le\sqrt{v}+A u ≤ v + A . Its truth value is determined by the signs of
A , v − A 2 , u − v − A 2 , ( u − v − A 2 ) 2 − 4 A 2 v . A,\qquad v-A^2,\qquad u-v-A^2,\qquad(u-v-A^2)^2-4A^2v. A , v − A 2 , u − v − A 2 , ( u − v − A 2 ) 2 − 4 A 2 v . Indeed, the only point to be careful about is that one cannot square an inequality unless the relevant side is known to be nonnegative. The signs of A A A and v − A 2 v-A^2 v − A 2 handle these case distinctions. Once the valid squaring step is determined, the signs of u − v − A 2 u-v-A^2 u − v − A 2 and ( u − v − A 2 ) 2 − 4 A 2 v (u-v-A^2)^2-4A^2v ( u − v − A 2 ) 2 − 4 A 2 v decide the remaining comparison.
These polynomials have degree at most 4 in ( C , β ) (C,\beta) ( C , β ) . There are s = O ( k d ) s=O(kd) s = O ( k d ) real variables. For each point p ℓ p_\ell p ℓ , the sign of F C , β ( p ℓ ) − τ ℓ F_{C,\beta}(p_\ell)-\tau_\ell F C , β ( p ℓ ) − τ ℓ is determined by the signs of O ( k 2 ) O(k^2) O ( k 2 ) constant-degree polynomials: these account for the possible minimizers at p ℓ p_\ell p ℓ and at its anchor, and for the comparison between the two chosen values.
Thus, over all m m m points, the threshold signs are determined by N p o l y = O ( m k 2 ) N_{\mathrm{poly}}=O(mk^2) N poly = O ( m k 2 ) constant-degree polynomials. Warren’s theorem implies that the number of possible threshold patterns is at most
( C 0 N p o l y s ) s . \left(\frac{C_0N_{\mathrm{poly}}}{s}\right)^s. ( s C 0 N poly ) s . If the m m m points are pseudo-shattered, then this number is at least 2 m 2^m 2 m . Since s = O ( k d ) s=O(kd) s = O ( k d ) , this gives m = O ~ ( k d ) m=\widetilde{O}(kd) m = O ( k d ) .
Lemma 6.6 (Error before rescaling). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ ε W 1 . \sup_{C,\beta}\left|\sum_{q\in Q}\widehat{w}_q g_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right|\lesssim\varepsilon W_1. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ ε W 1 . Proof. Let M M M be the total number of points sampled by the algorithm and let D = pdim ( F ) D=\operatorname{pdim}(\mathcal{F}) D = pdim ( F ) . By Lemma B.4, applied to F \mathcal{F} F , together with Lemma 6.9 and Claim 6.8, with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ 1 M ∑ q ∈ Q F C , β ( q ) − 1 M ∑ q ∈ Q F C , β ( q ) ∣ ≲ D log M + log ( 1 / δ ) M . \sup_{C,\beta}\left|\frac{1}{M}\sum_{q\in Q}F_{C,\beta}(q)-\frac{1}{M}\sum_{q\in Q}F_{C,\beta}(q)\right|\lesssim\sqrt{\frac{D\log M+\log(1/\delta)}{M}}. C , β sup M 1 q ∈ Q ∑ F C , β ( q ) − M 1 q ∈ Q ∑ F C , β ( q ) ≲ M D log M + log ( 1/ δ ) . Using Equation (19) , this gives
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ W 1 T M ( D log M + log ( 1 / δ ) ) . \sup_{C,\beta}\left|\sum_{q\in Q}\widehat{w}_q g_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right|\lesssim\frac{W_1}{T}\sqrt{M\left(D\log M+\log(1/\delta)\right)}. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ T W 1 M ( D log M + log ( 1/ δ ) ) . Since D = O ~ ( k d ) D=\widetilde{O}(kd) D = O ( k d ) , M = O ~ ( T ) M=\widetilde{O}(T) M = O ( T ) , and T = Θ ~ ( k ε − 2 ( d + log ( 1 / δ ) ) ) T=\widetilde{\Theta}(k\varepsilon^{-2}(d+\log(1/\delta))) T = Θ ( k ε − 2 ( d + log ( 1/ δ ))) , the RHS is at most O ( ε ) W 1 O(\varepsilon)W_1 O ( ε ) W 1 .
Lemma 6.7 (Rescaling error). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε W 1 . \sup_{C,\beta}\left|\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon W_1. C , β sup q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε W 1 . Proof. Fix j ∈ [ k ] j\in[k] j ∈ [ k ] . By the triangle inequality,
∣ ∑ q ∈ Q j ( w q − w ^ q ) g C , β ( q ) ∣ ≤ ∑ q ∈ Q j ∣ w q − w ^ q ∣ ∣ g C , β ( q ) ∣ ≲ ε ∑ q ∈ Q j w ^ q r q . (23) \left|\sum_{q\in Q_j}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\leq\sum_{q\in Q_j}|w_q-\widehat{w}_q||g_{C,\beta}(q)|\lesssim\varepsilon\sum_{q\in Q_j}\widehat{w}_q r_q. \tag*{(23)} q ∈ Q j ∑ ( w q − w q ) g C , β ( q ) ≤ q ∈ Q j ∑ ∣ w q − w q ∣∣ g C , β ( q ) ∣ ≲ ε q ∈ Q j ∑ w q r q . (23) The last inequality uses property (iii) of Claim 6.3 and the bound ∣ g C , β ( q ) ∣ ≤ r q |g_{C,\beta}(q)|\leq r_q ∣ g C , β ( q ) ∣ ≤ r q from Equation (16) . For every sampled point q ∈ P j q\in P_j q ∈ P j ,
w ^ q r q = r q m j π j ( q ) ≤ 2 Φ j m j . \widehat{w}_q r_q=\frac{r_q}{m_j\pi_j(q)}\leq\frac{2\Phi_j}{m_j}. w q r q = m j π j ( q ) r q ≤ m j 2 Φ j . because π j ( q ) ≥ r q / ( 2 Φ j ) \pi_j(q)\geq r_q/(2\Phi_j) π j ( q ) ≥ r q / ( 2 Φ j ) . Therefore
∑ q ∈ Q j w ^ q r q ≤ 2 Φ j . (24) \sum_{q\in Q_j}\widehat{w}_q r_q\leq2\Phi_j. \tag*{(24)} q ∈ Q j ∑ w q r q ≤ 2 Φ j . (24) Summing (23) over all j ∈ [ k ] j\in[k] j ∈ [ k ] and using (24) yields,
∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε ∑ j ∈ [ k ] Φ j ≲ ε W 1 , \left|\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon\sum_{j\in[k]}\Phi_j\lesssim\varepsilon W_1, q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε j ∈ [ k ] ∑ Φ j ≲ ε W 1 , which completes the proof.
Euclidean Capacitated k k k -means
We next prove the Euclidean coreset theorem for capacitated k k k -means.
Theorem 7.1 (Euclidean capacitated k k k -means). Let P ⊆ R d P \subseteq\mathbb{R}^{d} P ⊆ R d be a set of n n n points. For every ε , δ ∈ ( 0 , 1 ) \varepsilon, \delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , there is an algorithm which outputs a weighted subset Q ⊆ P Q \subseteq P Q ⊆ P of size
∣ Q ∣ = O ~ ( k ε − 6 + k ε − 4 log ( 1 / δ ) ) |Q| = \widetilde{O}\left(k\varepsilon^{-6} + k\varepsilon^{-4}\log(1/\delta)\right) ∣ Q ∣ = O ( k ε − 6 + k ε − 4 log ( 1/ δ ) ) such that, with probability at least 1 − δ 1-\delta 1 − δ , Q Q Q is an ε \varepsilon ε -coreset for Euclidean capacitated k k k -means.
As in the Euclidean k k k -median section, it is enough to prove a dimension-dependent coreset bound. The reduction from the dimension-dependent bound to Theorem 7.1 is in Section C.2.
Lemma 7.2 (Dimension-dependent coreset). There is an algorithm, which with probability at least 1 − δ 1-\delta 1 − δ outputs an ε \varepsilon ε -coreset Q ⊆ P Q \subseteq P Q ⊆ P for Euclidean capacitated k k k -means of size
O ~ ( k d ε − 4 + k ε − 4 log ( 1 / δ ) ) . \widetilde{O}\left(kd\varepsilon^{-4} + k\varepsilon^{-4}\log(1/\delta)\right). O ( k d ε − 4 + k ε − 4 log ( 1/ δ ) ) .
Mass-Preserving Sensitivity Sampling
We use the same reference clusters as in the Euclidean k k k -median section, but with a squared reference scale. Let A = { a 1 , … , a k } ⊆ R d A=\{a_1,\ldots,a_k\}\subseteq\mathbb{R}^{d} A = { a 1 , … , a k } ⊆ R d be an O ( 1 ) O(1) O ( 1 ) -approximate unconstrained Euclidean k k k -means solution for P P P . For j ∈ [ k ] j\in[k] j ∈ [ k ] , let P j P_j P j be the set of points in P P P whose nearest anchor in A A A is a j a_j a j , with ties broken arbitrarily. For each p ∈ P j p\in P_j p ∈ P j , define r p = ∥ p − a j ∥ r_p=\lVert p-a_j\rVert r p = ∥ p − a j ∥ , and let
Φ j = ∑ p ∈ P j r p 2 , W 2 = ∑ j ∈ [ k ] Φ j ≲ O P T , \Phi_j=\sum_{p\in P_j}r_p^2,\qquad W_2=\sum_{j\in[k]}\Phi_j\lesssim\mathrm{OPT}, Φ j = p ∈ P j ∑ r p 2 , W 2 = j ∈ [ k ] ∑ Φ j ≲ OPT ,
where OPT denotes the optimum unconstrained Euclidean k k k -means cost of P P P .
The sampler is the same as in Algorithm 2, with r p 2 r_p^2 r p 2 replacing r p r_p r p . Thus, for every cluster P j P_j P j with Φ j > 0 \Phi_j>0 Φ j > 0 , we sample a multiset Q j Q_j Q j of m j = ⌈ T Φ j / W 2 ⌉ + m 0 m_j=\lceil T\Phi_j/W_2\rceil+m_0 m j = ⌈ T Φ j / W 2 ⌉ + m 0 points independently from
π j ( p ) = 1 2 ( 1 ∣ P j ∣ + r p 2 Φ j ) , p ∈ P j , \pi_j(p)=\frac{1}{2}\left(\frac{1}{|P_j|}+\frac{r_p^2}{\Phi_j}\right),\qquad p\in P_j, π j ( p ) = 2 1 ( ∣ P j ∣ 1 + Φ j r p 2 ) , p ∈ P j ,
where T = Θ ~ ( k ε − 4 ( d + log ( 1 / δ ) ) ) T=\widetilde{\Theta}(k\varepsilon^{-4}(d+\log(1/\delta))) T = Θ ( k ε − 4 ( d + log ( 1/ δ ))) and m 0 = Θ ( ε − 4 log ( k / δ ) ) m_0=\Theta(\varepsilon^{-4}\log(k/\delta)) m 0 = Θ ( ε − 4 log ( k / δ )) .
Each sampled occurrence q ∈ Q j q\in Q_j q ∈ Q j receives initial weight w ^ q = ( m j π j ( q ) ) − 1 \widehat{w}_q=(m_j\pi_j(q))^{-1} w q = ( m j π j ( q ) ) − 1 . The weights inside each cluster are then rescaled so that the final total weight of the samples from P j P_j P j is exactly ∣ P j ∣ |P_j| ∣ P j ∣ . We use w q w_q w q to denote the weight of the point after rescaling.
We note the analogue of Claim 6.3 , with essentially the same proof. The initial weights preserve each cluster size up to a ( 1 ± ε 2 ) (1\pm\varepsilon^2) ( 1 ± ε 2 ) factor, which will be important when bounding the rescaling error. This stronger concentration follows from the choice m 0 = Θ ( ε − 4 log ( k / δ ) ) m_0=\Theta(\varepsilon^{-4}\log(k/\delta)) m 0 = Θ ( ε − 4 log ( k / δ )) , which ensures that sufficiently many samples are drawn from each cluster.
Claim 7.3 (Cluster Mass Preservation for k k k -means). The following properties hold.
(i) (Initial Weights ) With probability at least 1 − δ 1-\delta 1 − δ , for all j ∈ [ k ] j\in[k] j ∈ [ k ] , ∑ q ∈ Q j w ^ q = ( 1 ± ε 2 ) ∣ P j ∣ \sum_{q\in Q_j}\widehat{w}_q=(1\pm\varepsilon^2)|P_j| ∑ q ∈ Q j w q = ( 1 ± ε 2 ) ∣ P j ∣ .
(ii) (Final Weights ) With probability 1 1 1 , for all j ∈ [ k ] j\in[k] j ∈ [ k ] , ∑ q ∈ Q j w q = ∣ P j ∣ \sum_{q\in Q_j}w_q=|P_j| ∑ q ∈ Q j w q = ∣ P j ∣ .
(iii) If the event in (i) occurs, then for all q ∈ Q q\in Q q ∈ Q , ∣ w q − w ^ q ∣ ≲ ε 2 w ^ q |w_q-\widehat{w}_q|\lesssim\varepsilon^2\widehat{w}_q ∣ w q − w q ∣ ≲ ε 2 w q .
Analysis
Our goal is to prove Lemma 7.2 . The argument is the same as for Euclidean k k k -median, except that we first truncate far point-center costs.
Truncation. For p ∈ P j p \in P_j p ∈ P j , define the truncated squared cost of assigning p p p to center c i c_i c i by
ℓ ~ i ( p ) = { ∥ p − c i ∥ 2 , if ∥ a j − c i ∥ ≤ r p / ε , ∥ a j − c i ∥ 2 , otherwise. \widetilde{\ell}_i(p) =
\begin{cases}
\lVert p-c_i\rVert^2, & \text{if }\lVert a_j-c_i\rVert\le r_p/\varepsilon,\\
\lVert a_j-c_i\rVert^2, & \text{otherwise.}
\end{cases} ℓ i ( p ) = { ∥ p − c i ∥ 2 , ∥ a j − c i ∥ 2 , if ∥ a j − c i ∥ ≤ r p / ε , otherwise.
For a weighted instance S S S supported on P P P , let cost ~ S ( C , h ) \widetilde{\operatorname{cost}}_S(C,h) cost S ( C , h ) denote the cost using the truncated costs ℓ ~ i \widetilde{\ell}_i ℓ i . By the same pointwise argument as in Lemma 5.4 , for every such S S S , every C ∈ ( R d ) k C \in(\mathbb{R}^d)^k C ∈ ( R d ) k , and every h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
cost ~ S ( C , h ) = ( 1 ± O ( ε ) ) cost S ( C , h ) . (25) \widetilde{\operatorname{cost}}_S(C,h)=(1\pm O(\varepsilon))\operatorname{cost}_S(C,h). \tag*{(25)} cost S ( C , h ) = ( 1 ± O ( ε )) cost S ( C , h ) . (25)
Centered truncated dual error. For the rest of the analysis, the dual quantities f C , β f_{C,\beta} f C , β , Dual S ( C , h , β ) \operatorname{Dual}_S(C,h,\beta) Dual S ( C , h , β ) , and Err C ( β ) \operatorname{Err}_C(\beta) Err C ( β ) are interpreted with respect to the truncated edge costs ℓ ~ i \widetilde{\ell}_i ℓ i . When evaluating f C , β f_{C,\beta} f C , β at an anchor a j a_j a j , the edge cost to c i c_i c i is ∥ a j − c i ∥ 2 \lVert a_j-c_i\rVert^2 ∥ a j − c i ∥ 2 .
For p ∈ P j p \in P_j p ∈ P j , define
g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) . g_{C,\beta}(p)=f_{C,\beta}(p)-f_{C,\beta}(a_j). g C , β ( p ) = f C , β ( p ) − f C , β ( a j ) .
The centered-range bound from the finite-metric k k k -means analysis gives
∣ g C , β ( p ) ∣ ≲ ε − 1 r p 2 . (26) \lvert g_{C,\beta}(p)\rvert\lesssim\varepsilon^{-1}r_p^2. \tag*{(26)} ∣ g C , β ( p )∣ ≲ ε − 1 r p 2 . (26)
By the same dual-to-primal implication as Lemma 6.4 , applied to the truncated costs, it is enough to prove
sup C , β ∣ Err C ( β ) ∣ ≲ ε W 2 . (27) \sup_{C,\beta}\lvert\operatorname{Err}_C(\beta)\rvert\lesssim\varepsilon W_2. \tag*{(27)} C , β sup ∣ Err C ( β )∣ ≲ ε W 2 . (27)
Indeed, this gives
∣ cost ~ Q ( C , h ) − cost ~ P ( C , h ) ∣ ≲ ε W 2 ≲ ε cost P ( C , h ) , \left\lvert\widetilde{\operatorname{cost}}_Q(C,h)-\widetilde{\operatorname{cost}}_P(C,h)\right\rvert\lesssim\varepsilon W_2 \lesssim\varepsilon\operatorname{cost}_P(C,h), cost Q ( C , h ) − cost P ( C , h ) ≲ ε W 2 ≲ ε cost P ( C , h ) ,
using W 2 ≲ OPT ≤ cost P ( C , h ) W_2\lesssim\operatorname{OPT}\le\operatorname{cost}_P(C,h) W 2 ≲ OPT ≤ cost P ( C , h ) , and then (25) transfers the guarantee from cost to cost. As in the Euclidean k k k -median analysis (see Claim 6.5), cluster-wise mass preservation (Claim 7.3 ) implies
Err C ( β ) = ∑ q ∈ Q w q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) . (28) \operatorname{Err}_C(\beta)=\sum_{q\in Q}w_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p). \tag*{(28)} Err C ( β ) = q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) . (28)
Combining this identity with the same initial/final weight decomposition as in Equation (17) , it is enough to prove the following two estimates.
Lemma 7.4 (Error before rescaling). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ ε W 2 . \sup_{C,\beta}\left\lvert\sum_{q\in Q}\widehat{w}_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right\rvert\lesssim\varepsilon W_2. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ ε W 2 .
Lemma 7.5 (Rescaling error). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε W 2 . \sup_{C,\beta}\left\lvert\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right\rvert\lesssim\varepsilon W_2. C , β sup q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε W 2 .
Together, the two estimates imply (27) with probability at least 1 − δ 1-\delta 1 − δ . By the reduction above, this gives the coreset guarantee of Lemma 7.2 for Euclidean k k k -means. Thus it remains only to prove Lemma 7.4 and Lemma 7.5.
Bounding the Error Before Rescaling: Proof of Lemma 7.4
For each set of centers C C C and dual vector β \beta β , define the function
F C , β ( p ) = ε T C 0 W 2 w ^ p g C , β ( p ) , (29) F_{C,\beta}(p) = \frac{\varepsilon T}{C_0W_2}\widehat{w}_p g_{C,\beta}(p), \tag*{(29)} F C , β ( p ) = C 0 W 2 εT w p g C , β ( p ) , (29)
where C 0 C_0 C 0 is a sufficiently large universal constant. In the above equation, for a point p p p in cluster P j P_j P j we use w ^ p = 1 / ( m j π j ( p ) ) \widehat{w}_p = 1/(m_j\pi_j(p)) w p = 1/ ( m j π j ( p )) . This is the initial weight assigned if p p p is sampled. The point of defining F F F is that we can express the error before weight rescaling in terms of F F F :
∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) = C 0 W 2 ε T ( ∑ q ∈ Q F C , β ( q ) − ∑ q ∈ Q E F C , β ( q ) ) . (30) \sum_{q\in Q}\widehat{w}_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)=\frac{C_0W_2}{\varepsilon T}\left(\sum_{q\in Q}F_{C,\beta}(q)-\sum_{q\in Q}\mathbb{E}F_{C,\beta}(q)\right). \tag*{(30)} q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) = εT C 0 W 2 q ∈ Q ∑ F C , β ( q ) − q ∈ Q ∑ E F C , β ( q ) . (30)
The normalization factor ε T / ( C 0 W 2 ) \varepsilon T/(C_0W_2) εT / ( C 0 W 2 ) in (29) is chosen so that F C , β F_{C,\beta} F C , β is bounded by 1.
Claim 7.6. For every C , β C,\beta C , β , and every p ∈ P p\in P p ∈ P , ∣ F C , β ( p ) ∣ ≤ 1 |F_{C,\beta}(p)|\leq1 ∣ F C , β ( p ) ∣ ≤ 1 . Indeed, this follows from the proof of Claim 6.8, using Equation (26) , π j ( p ) ≥ r p 2 / ( 2 Φ j ) \pi_j(p)\geq r_p^2/(2\Phi_j) π j ( p ) ≥ r p 2 / ( 2 Φ j ) , and m j ≥ T Φ j / W 2 m_j\geq T\Phi_j/W_2 m j ≥ T Φ j / W 2 , with C 0 C_0 C 0 chosen sufficiently large.
We now bound the pseudo-dimension of the following function class:
F = { F C , β : C ∈ ( R d ) k , β ∈ R k } . (31) \mathcal{F}=\{F_{C,\beta}:C\in(\mathbb{R}^d)^k,\ \beta\in\mathbb{R}^k\}. \tag*{(31)} F = { F C , β : C ∈ ( R d ) k , β ∈ R k } . (31)
Lemma 7.7. pdim ( F ) = O ~ ( k d ) \operatorname{pdim}(\mathcal{F})=\widetilde{O}(kd) pdim ( F ) = O ( k d ) .
Proof. This is the same Warren-theorem argument as in Lemma 6.9 . The pointwise factor in (29) is fixed once p p p is fixed, so it does not affect the sign-pattern argument.
The only difference is that the threshold comparisons now involve truncated squared costs. These comparisons are determined by squared-cost inequalities
∥ x − c s ∥ 2 + β s ≤ ∥ y − c t ∥ 2 + β t + θ \lVert x-c_s\rVert^2+\beta_s\leq\lVert y-c_t\rVert^2+\beta_t+\theta ∥ x − c s ∥ 2 + β s ≤ ∥ y − c t ∥ 2 + β t + θ and near/far predicates
∥ a j − c s ∥ 2 ≤ r p 2 / ε 2 . \lVert a_j-c_s\rVert^2\leq r_p^2/\varepsilon^2. ∥ a j − c s ∥ 2 ≤ r p 2 / ε 2 . All of these are constant-degree polynomial inequalities in ( C , β ) (C,\beta) ( C , β ) . Thus, for m m m fixed points and thresholds, all threshold signs are determined by O ( m k 2 ) O(mk^2) O ( m k 2 ) constant-degree polynomials in O ( k ( d + 1 ) ) O(k(d+1)) O ( k ( d + 1 )) variables. Warren’s theorem gives pdim ( F ) = O ~ ( k d ) \operatorname{pdim}(\mathcal{F})=\widetilde{O}(kd) pdim ( F ) = O ( k d ) .
Lemma 7.4 (Error before rescaling). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ ε W 2 . \sup_{C,\beta}\left|\sum_{q\in Q}\widehat{w}_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right|\lesssim\varepsilon W_2. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ ε W 2 . Proof. Let M M M be the total number of points sampled by the algorithm and let D = pdim ( F ) D=\operatorname{pdim}(\mathcal{F}) D = pdim ( F ) . By Lemma B.4, applied to F \mathcal{F} F , together with Claim 7.6 , Lemma 7.7 , and Equation (30) , with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q w ^ q g C , β ( q ) − ∑ p ∈ P g C , β ( p ) ∣ ≲ W 2 ε T M ( D log M + log ( 1 / δ ) ) ≲ ε W 2 . \sup_{C,\beta}\left|\sum_{q\in Q}\widehat{w}_qg_{C,\beta}(q)-\sum_{p\in P}g_{C,\beta}(p)\right|\lesssim\frac{W_2}{\varepsilon T}\sqrt{M\bigl(D\log M+\log(1/\delta)\bigr)}\lesssim\varepsilon W_2. C , β sup q ∈ Q ∑ w q g C , β ( q ) − p ∈ P ∑ g C , β ( p ) ≲ εT W 2 M ( D log M + log ( 1/ δ ) ) ≲ ε W 2 . as D = O ~ ( k d ) D=\widetilde{O}(kd) D = O ( k d ) , M = O ~ ( T ) M=\widetilde{O}(T) M = O ( T ) , and T = Θ ~ ( k ε − 4 ( d + log ( 1 / δ ) ) ) T=\widetilde{\Theta}(k\varepsilon^{-4}(d+\log(1/\delta))) T = Θ ( k ε − 4 ( d + log ( 1/ δ ))) .
Bounding Rescaling Error: Proof of lem:euclidean-kmeans-rescaling-error
Lemma 7.5 (Rescaling error). With probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 ,
sup C , β ∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε W 2 . \sup_{C,\beta}\left|\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon W_2. C , β sup q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε W 2 . Proof. This is the same argument as in the Euclidean k k k -median rescaling proof. By Claim 7.3 , with probability at least 1 − δ / 2 1-\delta/2 1 − δ /2 , we have ∣ w q − w ^ q ∣ ≲ ε 2 w ^ q |w_q-\widehat{w}_q|\lesssim\varepsilon^2\widehat{w}_q ∣ w q − w q ∣ ≲ ε 2 w q for every q ∈ Q q\in Q q ∈ Q . Together with Equation (26) , this gives, for every j ∈ [ k ] j\in[k] j ∈ [ k ] ,
∣ ∑ q ∈ Q j ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε ∑ q ∈ Q j w ^ q r q 2 . \left|\sum_{q\in Q_j}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon\sum_{q\in Q_j}\widehat{w}_q r_q^2. q ∈ Q j ∑ ( w q − w q ) g C , β ( q ) ≲ ε q ∈ Q j ∑ w q r q 2 . Moreover, since π j ( q ) ≥ r q 2 / ( 2 Φ j ) \pi_j(q)\ge r_q^2/(2\Phi_j) π j ( q ) ≥ r q 2 / ( 2 Φ j ) , we have w ^ q r q 2 ≤ 2 Φ j / m j \widehat{w}_q r_q^2\le2\Phi_j/m_j w q r q 2 ≤ 2 Φ j / m j for every q ∈ Q j q\in Q_j q ∈ Q j , and hence ∑ q ∈ Q j w ^ q r q 2 ≤ 2 Φ j \sum_{q\in Q_j}\widehat{w}_q r_q^2\le2\Phi_j ∑ q ∈ Q j w q r q 2 ≤ 2 Φ j . Summing over j ∈ [ k ] j\in[k] j ∈ [ k ] gives
∣ ∑ q ∈ Q ( w q − w ^ q ) g C , β ( q ) ∣ ≲ ε ∑ j ∈ [ k ] Φ j = ε W 2 . \left|\sum_{q\in Q}(w_q-\widehat{w}_q)g_{C,\beta}(q)\right|\lesssim\varepsilon\sum_{j\in[k]}\Phi_j=\varepsilon W_2. q ∈ Q ∑ ( w q − w q ) g C , β ( q ) ≲ ε j ∈ [ k ] ∑ Φ j = ε W 2 .
Acknowledgements
Milind Prabhu was supported by the NSF grant CCF-2327011. Chris Schwiegelsohn and Sudarshan Shyam were supported in part by a Google Research Award. Erik Waingarten was supported by the NSF grant CCF-2337993.
Related Work
The first coreset definition as it is nowadays understood for clustering problems was given by Har-Peled and Mazumdar [30 ] . Initially, the techniques were mainly focused on low-dimensional Euclidean spaces [21 , 26 ] , and are still an active area of research today [2 , 23 ] . Chen’s seminal paper [10 ] brought sampling and learning theory to coresets, initially mostly via uniform sampling. Feldman, Langberg, and Schulman [20 , 32 ] then introduced the sensitivity sampling distribution, arguably the definitive algorithm in this line of work. Thereafter, for almost a decade, most coreset papers either focused on dimension reduction techniques for high dimensional Euclidean spaces [3 CW25, 22 , 33 , 40 , 19 ] , or by applying the sensitivity sampling framework to other metrics such as doubling metrics [24 ] , graph metrics [8 , 4 ] , or metrics on time series [11 HSV21, MRSS26] . Cohen-Addad, Saulpic, and Schwiegelshohn [15 ] proposed the group sampling algorithm, which ultimately yielded optimal coreset bounds for most of these problems [9 , 14 , 13 , 29 ] . It later turned out that sensitivity sampling is likewise optimal [6 PSS26a] , empirically preferable [SS22], fault tolerant [PSS26b], and can be implemented extremely efficiently [17 , 27 , 18 ] in various settings.
Concentration Inequalities
We first state two standard concentration inequalities.
Lemma B.1 (Hoeffding’s inequality [42 Theorem 2.2.6] ). Let Z 1 , … , Z m Z_1,\ldots,Z_m Z 1 , … , Z m be independent mean-zero random variables. Suppose that there exists a constant M > 0 M > 0 M > 0 such that ∣ Z j ∣ ≤ M |Z_j| \le M ∣ Z j ∣ ≤ M almost surely for all j ∈ [ m ] j \in[m] j ∈ [ m ] . Then, for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
∣ ∑ j = 1 m Z j ∣ ≤ 2 m M 2 log 2 δ . \left|\sum_{j=1}^{m} Z_j\right| \le\sqrt{2mM^2\log\frac{2}{\delta}}. j = 1 ∑ m Z j ≤ 2 m M 2 log δ 2 .
Lemma B.2 (Bernstein’s inequality [42 Theorem 2.9.5] ). Let Z 1 , … , Z m Z_1,\ldots,Z_m Z 1 , … , Z m be independent mean-zero random variables. Suppose there exists a constant M > 0 M > 0 M > 0 such that ∣ Z j ∣ ≤ M |Z_j| \le M ∣ Z j ∣ ≤ M almost surely for all j ∈ [ m ] j \in[m] j ∈ [ m ] , and define
V = ∑ j = 1 m E [ Z j 2 ] . V=\sum_{j=1}^{m}\mathbb{E}[Z_j^2]. V = j = 1 ∑ m E [ Z j 2 ] . Then, for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
∣ ∑ j = 1 m Z j ∣ ≤ V log 2 δ + M log 2 δ . \left|\sum_{j=1}^{m} Z_j\right| \le\sqrt{V\log\frac{2}{\delta}}+M\log\frac{2}{\delta}. j = 1 ∑ m Z j ≤ V log δ 2 + M log δ 2 .
Concentration via Pseudo-dimension
In the Euclidean sections, we need uniform concentration for families of normalized sampled summands indexed by the centers and dual variables. We use a standard two-step approach: first bound the pseudo-dimension of the relevant function class, and then apply a uniform convergence bound for bounded real-valued functions. The pseudo-dimension bounds are obtained by showing that each threshold comparison is determined by the signs of a bounded number of low-degree polynomials, and then applying Warren’s theorem. This appendix collects the common tools used in both the Euclidean k k k -median and Euclidean k k k -means analyses.
Definition B.3 (Pseudo-dimension). Let F \mathcal{F} F be a class of real-valued functions on a domain X \mathcal{X} X . A set S = { x 1 , … , x m } ⊆ X S = \{x_1,\ldots,x_m\} \subseteq\mathcal{X} S = { x 1 , … , x m } ⊆ X is pseudo-shattered by F \mathcal{F} F if there are thresholds τ 1 , … , τ m ∈ R \tau_1,\ldots,\tau_m \in\mathbb{R} τ 1 , … , τ m ∈ R such that, for every I ⊆ [ m ] I \subseteq[m] I ⊆ [ m ] , there is f ∈ F f \in\mathcal{F} f ∈ F satisfying
f ( x i ) ≥ τ i for i ∈ I , f ( x i ) < τ i for i ∉ I . f(x_i) \ge\tau_i \quad\text{for } i \in I,\qquad f(x_i) < \tau_i \quad\text{for } i \notin I. f ( x i ) ≥ τ i for i ∈ I , f ( x i ) < τ i for i ∈ / I .
The pseudo-dimension of F \mathcal{F} F , denoted pdim ( F ) \operatorname{pdim}(\mathcal{F}) pdim ( F ) , is the largest size of a set pseudo-shattered by F \mathcal{F} F .
The following lemma is a uniform convergence bound for bounded real-valued classes of finite pseudo-dimension; see, for ex., [1 Chapter 11] and [41 Chapter 2.6] .
Lemma B.4 (Uniform convergence). Let F \mathcal{F} F be a class of real-valued functions with pdim ( F ) ≤ D \operatorname{pdim}(\mathcal{F}) \le D pdim ( F ) ≤ D . Let Z 1 , … , Z m Z_1,\ldots,Z_m Z 1 , … , Z m be independent random variables, not necessarily identically distributed. Suppose that every f ∈ F f \in\mathcal{F} f ∈ F satisfies ∣ f ( Z t ) ∣ ≤ 1 |f(Z_t)| \le1 ∣ f ( Z t ) ∣ ≤ 1 for every t t t . Then, with probability at least 1 − δ 1-\delta 1 − δ ,
sup f ∈ F ∣ 1 m ∑ t = 1 m f ( Z t ) − 1 m ∑ t = 1 m E f ( Z t ) ∣ ≲ D log m + log ( 1 / δ ) m . \sup_{f\in\mathcal{F}}\left|\frac{1}{m}\sum_{t=1}^{m}f(Z_t)-\frac{1}{m}\sum_{t=1}^{m}\mathbb{E}f(Z_t)\right|
\lesssim\sqrt{\frac{D\log m+\log(1/\delta)}{m}}. f ∈ F sup m 1 t = 1 ∑ m f ( Z t ) − m 1 t = 1 ∑ m E f ( Z t ) ≲ m D log m + log ( 1/ δ ) .
Bounding the pseudo-dimension of a function class directly is sometimes challenging. We will use Warren’s theorem as a standard tool for this purpose. It applies when the relevant threshold comparisons can be described by low-degree polynomial inequalities. For a real number x x x , let sign ( x ) = 1 \operatorname{sign}(x)=1 sign ( x ) = 1 if x ≥ 0 x\ge0 x ≥ 0 and sign ( x ) = − 1 \operatorname{sign}(x)=-1 sign ( x ) = − 1 otherwise.
Lemma B.5 (Warren’s theorem [43 ] ). Let P 1 , … , P M P_1,\ldots,P_M P 1 , … , P M be real polynomials in s s s variables, each of degree at most Δ \Delta Δ . If M ≥ s M\ge s M ≥ s , then the number of sign patterns ( sign ( P 1 ( x ) ) , … , sign ( P M ( x ) ) ) (\operatorname{sign}(P_1(x)),\ldots,\operatorname{sign}(P_M(x))) ( sign ( P 1 ( x )) , … , sign ( P M ( x ))) , over all x ∈ R s x\in\mathbb{R}^s x ∈ R s , is at most ( 4 e Δ M / s ) s (4e\Delta M/s)^s ( 4 e Δ M / s ) s .
Omitted Proofs
Reduction to Upper Capacities
We also briefly outline how coresets for clustering with exact demands implies coresets for upper-bounded capacitated clustering. Similar reductions apply to cardinality lower bounds and fair clustering. These reductions are folklore, but we include the argument for completeness and future reference.
Proposition C.1 (Reduction from exact demands to upper capacities). Let P P P be a point set, and let u = ( u 1 , … , u k ) u=(u_1,\ldots,u_k) u = ( u 1 , … , u k ) be an upper-capacity vector. Suppose that Q Q Q is an ϵ \epsilon ϵ -coreset for P P P with respect to exact demand vectors h h h , meaning that for every set of centers C C C and every feasible demand vector h h h ,
( 1 − ϵ ) cost P ( C , h ) ≤ cost Q ( C , h ) ≤ ( 1 + ϵ ) cost P ( C , h ) . (1-\epsilon)\operatorname{cost}_P(C,h)\le\operatorname{cost}_Q(C,h)\le(1+\epsilon)\operatorname{cost}_P(C,h). ( 1 − ϵ ) cost P ( C , h ) ≤ cost Q ( C , h ) ≤ ( 1 + ϵ ) cost P ( C , h ) . Then Q Q Q is an ϵ \epsilon ϵ -coreset for P P P with respect to the upper-capacity constraints
∣ C i ∣ ≤ u i for all i ∈ { 1 , … , k } . |C_i|\le u_i\qquad\text{for all }i\in\{1,\ldots,k\}. ∣ C i ∣ ≤ u i for all i ∈ { 1 , … , k } .
Proof. Fix a set of centers C C C . The capacitated cost on P P P can be written as a minimization over exact demand vectors:
cost P cap ( C , u ) = min h : ∑ i h i = ∣ P ∣ 0 ≤ h i ≤ u i cost P ( C , h ) . \operatorname{cost}^{\operatorname{cap}}_P(C,u)
=
\min_{\substack{h:\,\sum_i h_i=|P|\\0\le h_i\le u_i}}
\operatorname{cost}_P(C,h). cost P cap ( C , u ) = h : ∑ i h i = ∣ P ∣ 0 ≤ h i ≤ u i min cost P ( C , h ) .
Similarly,
cost Q c a p ( C , u ) = min h : ∑ i h i = ∣ P ∣ 0 ≤ h i ≤ u i cost Q ( C , h ) . \operatorname{cost}^{\mathrm{cap}}_{Q}(C,u)=\min_{\substack{h:\sum_i h_i=|P|\\0\le h_i\le u_i}}\operatorname{cost}_{Q}(C,h). cost Q cap ( C , u ) = h : ∑ i h i = ∣ P ∣ 0 ≤ h i ≤ u i min cost Q ( C , h ) .
Let h P h_P h P be an exact demand vector attaining the minimum for P P P , and let h Q h_Q h Q be one attaining the minimum for Q Q Q . Then
cost Q c a p ( C , u ) = cost Q ( C , h Q ) ≤ cost Q ( C , h P ) ≤ ( 1 + ε ) cost P ( C , h P ) = ( 1 + ε ) cost P c a p ( C , u ) . \operatorname{cost}^{\mathrm{cap}}_{Q}(C,u)=\operatorname{cost}_{Q}(C,h_Q)\le\operatorname{cost}_{Q}(C,h_P)\le(1+\varepsilon)\operatorname{cost}_{P}(C,h_P)=(1+\varepsilon)\operatorname{cost}^{\mathrm{cap}}_{P}(C,u). cost Q cap ( C , u ) = cost Q ( C , h Q ) ≤ cost Q ( C , h P ) ≤ ( 1 + ε ) cost P ( C , h P ) = ( 1 + ε ) cost P cap ( C , u ) .
For the other direction,
cost Q c a p ( C , u ) = cost Q ( C , h Q ) ≥ ( 1 − ε ) cost P ( C , h Q ) ≥ ( 1 − ε ) cost P c a p ( C , u ) , \operatorname{cost}^{\mathrm{cap}}_{Q}(C,u)=\operatorname{cost}_{Q}(C,h_Q)\ge(1-\varepsilon)\operatorname{cost}_{P}(C,h_Q)\ge(1-\varepsilon)\operatorname{cost}^{\mathrm{cap}}_{P}(C,u), cost Q cap ( C , u ) = cost Q ( C , h Q ) ≥ ( 1 − ε ) cost P ( C , h Q ) ≥ ( 1 − ε ) cost P cap ( C , u ) ,
where the last inequality uses the fact that h Q h_Q h Q is feasible for the upper-capacitated problem on P P P . Therefore,
( 1 − ε ) cost P c a p ( C , u ) ≤ cost Q c a p ( C , u ) ≤ ( 1 + ε ) cost P c a p ( C , u ) , (1-\varepsilon)\operatorname{cost}^{\mathrm{cap}}_{P}(C,u)\le\operatorname{cost}^{\mathrm{cap}}_{Q}(C,u)\le(1+\varepsilon)\operatorname{cost}^{\mathrm{cap}}_{P}(C,u), ( 1 − ε ) cost P cap ( C , u ) ≤ cost Q cap ( C , u ) ≤ ( 1 + ε ) cost P cap ( C , u ) ,
as desired.
Dimension-Independent Coreset Bounds
In Lemma 6.2 and Lemma 7.2 , we proved dimension-dependent coreset bounds for Euclidean capacitated k k k -median and k k k -means. We now explain how to remove the dependence on the ambient dimension. The reduction has two standard ingredients. First, we use an existing Euclidean coreset construction to reduce the support size to poly ( k / ε ) \operatorname{poly}(k/\varepsilon) poly ( k / ε ) . Second, once the support is small, we use a terminal embedding to reduce the dimension to O ~ ( ε − 2 ) \widetilde{O}(\varepsilon^{-2}) O ( ε − 2 ) .
We use the small sized coresets as a black box.
Theorem C.2 (Polynomial-size Euclidean coresets [5 , 28 ] ). For Euclidean capacitated k k k -median and k k k -means, every instance P ⊆ R d P\subseteq\mathbb{R}^d P ⊆ R d admits an O ( ε ) O(\varepsilon) O ( ε ) -coreset S ⊆ P S\subseteq P S ⊆ P of size ∣ S ∣ = poly ( k / ε ) |S|=\operatorname{poly}(k/\varepsilon) ∣ S ∣ = poly ( k / ε ) .
We first replace the input points P P P by S S S , reducing the support size to poly ( k / ε ) \operatorname{poly}(k/\varepsilon) poly ( k / ε ) . Since coresets compose, it is enough to construct an O ( ε ) O(\varepsilon) O ( ε ) -coreset for S S S .
Here S S S is a weighted instance. Although the Euclidean dimension-dependent bounds were stated for unweighted inputs to avoid extra notation, the proofs extend verbatim to weighted inputs: replace cardinalities by total weights, replace sums by weighted sums, and perform the same cluster-wise rescaling with respect to the total weight of each reference cluster.
We next recall terminal embeddings. Unlike the Johnson–Lindenstrauss lemma, which preserves pairwise distances inside a finite point set, terminal embeddings preserve distances from a fixed finite terminal set to all query points in the ambient space.
Definition C.3 (Terminal embedding). Let T ⊆ R d T\subseteq\mathbb{R}^d T ⊆ R d be a finite terminal set. A map φ : R d → R d ′ \varphi:\mathbb{R}^d\to\mathbb{R}^{d'} φ : R d → R d ′ is a terminal embedding for T T T with distortion 1 + η 1+\eta 1 + η if, for every terminal t ∈ T t\in T t ∈ T and every query point y ∈ R d y\in\mathbb{R}^d y ∈ R d ,
∥ t − y ∥ ≤ ∥ φ ( t ) − φ ( y ) ∥ ≤ ( 1 + η ) ∥ t − y ∥ . \lVert t-y\rVert\le\lVert\varphi(t)-\varphi(y)\rVert\le(1+\eta)\lVert t-y\rVert. ∥ t − y ∥ ≤ ∥ φ ( t ) − φ ( y )∥ ≤ ( 1 + η ) ∥ t − y ∥ .
We use the following optimal terminal-embedding bound of Narayanan and Nelson [35 ] .
Theorem C.4. Let T ⊆ R d T\subseteq\mathbb{R}^d T ⊆ R d be a finite set of terminals. For every η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) , there is a terminal embedding φ : R d → R d ′ \varphi:\mathbb{R}^d\to\mathbb{R}^{d'} φ : R d → R d ′ for T T T with distortion 1 + η 1+\eta 1 + η , where
d ′ = O ( η − 2 log ∣ T ∣ ) . d'=O(\eta^{-2}\log|T|). d ′ = O ( η − 2 log ∣ T ∣ ) .
This is exactly the type of dimension reduction needed for clustering: the data points are the terminals, while the centers are arbitrary query points.
Lemma C.5. Let X ⊆ R d X \subseteq\mathbb{R}^d X ⊆ R d be a weighted instance, and let φ \varphi φ be a terminal embedding for the support of X X X with distortion 1 + η 1+\eta 1 + η . Then, for every center tuple C C C and every demand vector h ∈ n Δ k h \in n\Delta_k h ∈ n Δ k ,
cost φ ( X ) k -median ( φ ( C ) , h ) = ( 1 ± O ( η ) ) cost X k -median ( C , h ) , \operatorname{cost}^{k\text{-median}}_{\varphi(X)}(\varphi(C),h) = (1 \pm O(\eta))\operatorname{cost}^{k\text{-median}}_X(C,h), cost φ ( X ) k -median ( φ ( C ) , h ) = ( 1 ± O ( η )) cost X k -median ( C , h ) , and
cost φ ( X ) k -means ( φ ( C ) , h ) = ( 1 ± O ( η ) ) cost X k -means ( C , h ) . \operatorname{cost}^{k\text{-means}}_{\varphi(X)}(\varphi(C),h) = (1 \pm O(\eta))\operatorname{cost}^{k\text{-means}}_X(C,h). cost φ ( X ) k -means ( φ ( C ) , h ) = ( 1 ± O ( η )) cost X k -means ( C , h ) . Proof. For k k k -median, every point-center distance is preserved up to a 1 ± O ( η ) 1 \pm O(\eta) 1 ± O ( η ) factor. Hence the cost of every feasible exact-load assignment is preserved up to the same factor, and taking the minimum over assignments preserves the guarantee.
For k k k -means, the same distance preservation gives squared-distance preservation up to a 1 ± O ( η ) 1 \pm O(\eta) 1 ± O ( η ) factor, after adjusting constants. The same assignment-wise argument applies. □
Applying the reduction. For k k k -median, first replace P P P by the preliminary O ( ε ) O(\varepsilon) O ( ε ) -coreset S ⊆ P S \subseteq P S ⊆ P of size poly ( k / ε ) \operatorname{poly}(k/\varepsilon) poly ( k / ε ) . Apply Theorem C.4 to the support of S S S with η = Θ ( ε ) \eta= \Theta(\varepsilon) η = Θ ( ε ) , obtaining dimension
d ′ = O ( ε − 2 log ∣ S ∣ ) = O ~ ( ε − 2 ) . d' = O(\varepsilon^{-2}\log|S|) = \widetilde{O}(\varepsilon^{-2}). d ′ = O ( ε − 2 log ∣ S ∣ ) = O ( ε − 2 ) .
By Lemma C.5 , a coreset for the embedded instance can be pulled back to a coreset for S S S . Composing with the preliminary coreset then gives a coreset for P P P . Applying Lemma 6.2 in dimension d ′ d' d ′ therefore gives size
O ~ ( k d ′ ε − 2 + k ε − 2 log ( 1 / δ ) ) = O ~ ( k ε − 4 + k ε − 2 log ( 1 / δ ) ) , \widetilde{O}\left(kd'\varepsilon^{-2} + k\varepsilon^{-2}\log(1/\delta)\right) = \widetilde{O}\left(k\varepsilon^{-4} + k\varepsilon^{-2}\log(1/\delta)\right), O ( k d ′ ε − 2 + k ε − 2 log ( 1/ δ ) ) = O ( k ε − 4 + k ε − 2 log ( 1/ δ ) ) ,
as claimed in Theorem 6.1 . The three approximation losses are each set to a sufficiently small constant multiple of ε \varepsilon ε , so they compose to 1 ± ε 1 \pm\varepsilon 1 ± ε .
The proof for k k k -means is identical, using Lemma 7.2 instead; this gives size
O ~ ( k ε − 6 + k ε − 4 log ( 1 / δ ) ) , \widetilde{O}\left(k\varepsilon^{-6} + k\varepsilon^{-4}\log(1/\delta)\right), O ( k ε − 6 + k ε − 4 log ( 1/ δ ) ) ,
as claimed in Theorem 7.1 .