Introduction
Clustering is a fundamental task in geometry and data analysis, and it is commonly formulated as partitioning a dataset X X X k k k k k k k k k k k k k k k [43 , 44 ] .
Formally, in the min-sum k k k k k k n n n ( X , d i s t ) (X,\mathrm{dist}) ( X , dist ) k k k P = { P 1 , … , P k } \mathcal{P}=\{P_1,\ldots,P_k\} P = { P 1 , … , P k } X X X
cost ( P ) = ∑ i = 1 k ∑ x , y ∈ P i dist ( x , y ) . (1) \operatorname{cost}(\mathcal{P}) = \sum_{i=1}^{k} \sum_{x,y \in P_i} \operatorname{dist}(x,y). \tag*{(1)} cost ( P ) = i = 1 ∑ k x , y ∈ P i ∑ dist ( x , y ) . (1) To simplify notation, we sum over all ordered pairs, which includes every pair { x , y } ⊆ P i \{x,y\} \subseteq P_i { x , y } ⊆ P i X X X R d \mathbb{R}^d R d ℓ p \ell_p ℓ p Figure 1 . This effectiveness has led to increased interest in min-sum k k k [42 , 5 , 12 , 9 , 39 , 2 , 32 ] .
Figure 1. A min-sum k k k k k k k k k k = 2 k = 2 k = 2 R 2 \mathbb{R}^2 R 2 α > 1 \alpha> 1 α > 1 1 / α 1/\alpha 1/ α
Nevertheless, the known algorithmic tools for this objective are still lagging behind those for center-based objectives, which may explain why the min-sum objective is used much less in practice.
Notice that the total distance between all pairs of points in X X X (1) is equivalent to maximizing its complement, which is the (metric) Max-k k k k = 2 k = 2 k = 2
A sketch is a small or simple representation of the input that approximately preserves some quantities of interest. Sketching is a fundamental technique in algorithm design, and is especially important for processing large datasets, where it can significantly improve the running time, storage, and/or communication costs, which strongly depend on the size of the input representation.
Many different sketching methods were developed, and they have found numerous applications, from geometric optimization and numerical linear algebra to streaming and distributed computation [38 , 45 , 41 ] . We study sketches for min-sum k k k the sketch preserves the cost of all k k k This would follow easily from the much stronger requirement that all pairwise distances are preserved (multiplicatively). We study two common sketching approaches: dimension reduction for inputs in Euclidean R d \mathbb{R}^{d} R d d d d n n n k k k X X X k k k g : X → Y g:X\to Y g : X → Y ( Y , ρ ) (Y,\rho) ( Y , ρ ) A ⊆ X A\subseteq X A ⊆ X g ( A ) g(A) g ( A ) { g ( x ) ∣ x ∈ A } \{g(x)\mid x\in A\} { g ( x ) ∣ x ∈ A } k k k P = { P 1 , … , P k } \mathcal{P}=\{P_1,\ldots,P_k\} P = { P 1 , … , P k } X X X
g ( P ) = { g ( P 1 ) , … , g ( P k ) } . g(\mathcal{P})=\{g(P_1),\ldots,g(P_k)\}. g ( P ) = { g ( P 1 ) , … , g ( P k )} . We view this as a k k k g ( X ) g(X) g ( X ) g ( P i ) g(P_i) g ( P i ) g ( P j ) g(P_j) g ( P j ) i ≠ j i\ne j i = j
A useful way to measure the intrinsic geometry of a metric space X X X doubling dimension , denoted by ddim ( X ) \operatorname{ddim}(X) ddim ( X ) D ≥ 1 D\ge1 D ≥ 1 2 D 2^D 2 D [19 ] . This notion is effective even for inputs in Euclidean R d \mathbb{R}^{d} R d O ( d ) O(d) O ( d ) d d d aspect ratio of a set S ⊆ X S\subseteq X S ⊆ X
Δ = diam ( S ) min x ≠ y ∈ S dist ( x , y ) . \Delta=\frac{\operatorname{diam}(S)}{\min_{x\ne y\in S}\operatorname{dist}(x,y)}. Δ = min x = y ∈ S dist ( x , y ) diam ( S ) . where diam ( S ) = max x , y ∈ S dist ( x , y ) \operatorname{diam}(S)=\max_{x,y\in S}\operatorname{dist}(x,y) diam ( S ) = max x , y ∈ S dist ( x , y ) X X X
Dimension reduction. A standard sketching method is oblivious dimension reduction: When the input is a high-dimensional Euclidean point set, it is useful to project it to a low-dimensional space before running downstream applications like a clustering algorithm. This is a very powerful algorithmic tool, because the efficiency of many geometric algorithms depends heavily on the ambient dimension. The Johnson-Lindenstrauss (JL) Lemma [30 ] states that every n n n R t \mathbb{R}^{t} R t t = O ( ε − 2 log n ) t=O(\varepsilon^{-2}\log n) t = O ( ε − 2 log n ) 1 ± ε 1\pm\varepsilon 1 ± ε t t t [34 ] .
A standard oblivious construction, which we use below, is to apply a random linear map f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t
The JL guarantee on all pairwise distances clearly implies that also the min-sum cost of every partition is preserved up to the same factor. However, preserving all the pairwise distances might be an excessive requirement, and indeed dimension reduction tailored to clustering and related geometric optimization problems has been studied extensively. In particular, for center-based clustering such as k k k k k k t t t k k k n n n t = O ( ε − 2 log ( k / ε ) ) t=O(\varepsilon^{-2}\log(k/\varepsilon)) t = O ( ε − 2 log ( k / ε )) [6 , 10 , 3 , 36 ] .
The picture changes however when the center set is restricted: for k k k log log n \log\log n log log n [29 ] . For min-sum k k k x x x C C C O ( ∣ C ∣ ) O(|C|) O ( ∣ C ∣ ) x x x x x x x x x
Coresets. Another standard sketching method is a coreset, where the input X X X k k k X X X
Definition 1.1 (Movement-Based Coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) ( S , w ) (S,w) ( S , w ) S ⊆ X S \subseteq X S ⊆ X movement-based ε \varepsilon ε k k k X X X π : X → S \pi: X \to S π : X → S w ( s ) = ∣ π − 1 ( s ) ∣ w(s) = |\pi^{-1}(s)| w ( s ) = ∣ π − 1 ( s ) ∣ s ∈ S s \in S s ∈ S
∀ k -partition P of X , cost ( π ( P ) ) ∈ ( 1 ± ε ) cost ( P ) . \forall k\text{-partition }\mathcal{P}\text{ of }X,\qquad\operatorname{cost}(\pi(\mathcal{P})) \in(1 \pm\varepsilon)\operatorname{cost}(\mathcal{P}). ∀ k -partition P of X , cost ( π ( P )) ∈ ( 1 ± ε ) cost ( P ) . We call π \pi π movement rule ; it need not be stored explicitly as part of the coreset, i.e., the size of the coreset is ∣ S ∣ |S| ∣ S ∣ k k k S S S s ∈ S s \in S s ∈ S k k k s s s Claim 5.2 . Consequently, it suffices to solve the clustering problem on the small coreset ( S , w ) (S,w) ( S , w ) X X X S S S π − 1 ( s ) \pi^{-1}(s) π − 1 ( s ) X X X S S S
Definition 1.1 is analogous to the usual strong coreset guarantee for center-based clustering [22 , 17 , 7 ] , where a weighted set S S S X X X k k k X X X X X X [17 ] and for balanced k k k [4 ] (called a ”mapping coreset”), although their accuracy requirements are different and not suitable for our min-sum objective.
Previously, Czumaj and Sohler [12 ] proposed a very different definition of a coreset for min-sum k k k X X X S S S S S S X X X S S S X X X
Our Results
Our first two results are dimension-reduction bounds for min-sum k k k f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t N ( 0 , 1 / t ) N(0,1/t) N ( 0 , 1/ t )
Theorem 1.2 (Euclidean Dimension Reduction for Doubling Sets). *Let X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d k k k 0 < ε < 1 / 4 0 < \varepsilon< 1/4 0 < ε < 1/4 f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t
map, where t ≥ c ε − 2 ( ddim ( X ) log ( 1 / ε ) + log k + log log n ) t \ge c\varepsilon^{-2}(\operatorname{ddim}(X)\log(1/\varepsilon) + \log k + \log\log n) t ≥ c ε − 2 ( ddim ( X ) log ( 1/ ε ) + log k + log log n ) c > 0 c > 0 c > 0 4 / 5 4/5 4/5
∀ k -partition P of X , cost ( f ( P ) ) ∈ ( 1 ± ε ) cost ( P ) . \forall k\text{-partition } \mathcal{P}\text{ of }X,\qquad\operatorname{cost}(f(\mathcal{P})) \in(1 \pm\varepsilon)\operatorname{cost}(\mathcal{P}). ∀ k -partition P of X , cost ( f ( P )) ∈ ( 1 ± ε ) cost ( P ) . It is interesting to identify other parameters that can be used to guarantee dimension reduction. Surprisingly, we find that the aspect ratio can serve as such a parameter, in contrast to some other clustering objectives where standard lower-bound examples have aspect ratio O ( 1 ) O(1) O ( 1 )
Theorem 1.3 (Euclidean Dimension Reduction for Bounded Aspect Ratio). Let X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d k k k Δ \Delta Δ 0 < ε < 1 / 4 0 < \varepsilon< 1/4 0 < ε < 1/4 f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 ( log ( 1 / ε ) + log k + log Δ ) t \ge c\varepsilon^{-2}(\log(1/\varepsilon) + \log k + \log\Delta) t ≥ c ε − 2 ( log ( 1/ ε ) + log k + log Δ ) c > 0 c > 0 c > 0 4 / 5 4/5 4/5
∀ k -partition P of X , cost ( f ( P ) ) ∈ ( 1 ± ε ) cost ( P ) . \forall k\text{-partition } \mathcal{P}\text{ of }X,\qquad\operatorname{cost}(f(\mathcal{P})) \in(1 \pm\varepsilon)\operatorname{cost}(\mathcal{P}). ∀ k -partition P of X , cost ( f ( P )) ∈ ( 1 ± ε ) cost ( P ) . We remark that Theorems 1.2 and 1.3 immediately extend to objectives where pairwise distances are raised to power p ≥ 1 p \ge1 p ≥ 1 ∥ x − y ∥ 2 p \lVert x-y\rVert_{2}^{p} ∥ x − y ∥ 2 p t = O ( p 2 ε − 2 ( ddim ( X ) log ( p / ε ) + log k + log log n + p ) ) t = O(p^{2}\varepsilon^{-2}(\operatorname{ddim}(X)\log(p/\varepsilon) + \log k + \log\log n + p)) t = O ( p 2 ε − 2 ( ddim ( X ) log ( p / ε ) + log k + log log n + p )) t = O ( p 4 ε − 2 ( log ( p / ε ) + log k + p log ( Δ ) ) ) t = O(p^{4}\varepsilon^{-2}(\log(p/\varepsilon) + \log k + p\log(\Delta))) t = O ( p 4 ε − 2 ( log ( p / ε ) + log k + p log ( Δ ))) § 3.4 . An immediate corollary is that Schulman’s ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) ℓ 2 2 \ell_{2}^{2} ℓ 2 2 [42 ] , whose running time is exponential in the ambient dimension d d d t t t d d d
We further show that our bound on the target dimension in Theorem 1.2 is near-optimal (for Gaussian JL maps), namely, Ω ( ddim ( X ) ) \Omega(\operatorname{ddim}(X)) Ω ( ddim ( X )) n n n Ω ( ε − 2 log log n ) \Omega(\varepsilon^{-2}\log\log n) Ω ( ε − 2 log log n ) Theorem 3.10 .
Our next result is a movement-based coreset for min-sum k k k ( 1 / ε ) O ( ddim ) k log n (1/\varepsilon)^{O(\operatorname{ddim})}k\log n ( 1/ ε ) O ( ddim ) k log n
In comparison, the coreset of Czumaj and Sohler [12 ] achieves O ( 1 ) O(1) O ( 1 ) 1 + ε 1+\varepsilon 1 + ε poly ( k log n ) \operatorname{poly}(k\log n) poly ( k log n ) n n n
But as mentioned earlier, their definition of a coreset is very different and incomparable to ours.
Theorem 1.4 (Density-adaptive coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n ddim ≥ 1 \operatorname{ddim} \ge1 ddim ≥ 1 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 ε \varepsilon ε ( S , w ) (S,w) ( S , w )
∣ S ∣ ≤ ( 1 ε ) O ( ddim ) k log n , |S| \le\left(\frac{1}{\varepsilon}\right)^{O(\operatorname{ddim})} k\log n, ∣ S ∣ ≤ ( ε 1 ) O ( ddim ) k log n , whose movement rule is the nearest-neighbor map. Moreover, such a coreset can be constructed in randomized near-linear time with high probability.
We further show that the logarithmic dependence on n n n R \mathbb{R} R Ω ( log n ) \Omega(\log n) Ω ( log n ) Proposition 4.18 . To bypass this lower bound, one may follow the spirit of Theorem 1.3 and construct coresets according to our definition, whose size depends on other parameters, like the aspect ratio Δ \Delta Δ
Finally, we use our coreset results to derive two streaming algorithms, one for insertion-only streams and one for dynamic streams. Our algorithms estimate the optimum value of min-sum k k k OPT ( X ) \operatorname{OPT}(X) OPT ( X ) X X X X X X
In the insertion-only streaming model, the input X X X
Unfortunately, we cannot simply apply merge-and-reduce, which is a standard technique to devise a streaming algorithm from any coreset that has two properties called Merge and Reduce (see [22 , 41 ] ).
It is easy to see that movement-based coresets satisfy the following Reduce Property (summarized as “a coreset of a coreset is itself a coreset”): suppose S S S X X X T T T S S S T T T X X X
But unfortunately, movement-based coresets do not necessarily satisfy the following Merge Property (summarized as “the union of coresets is a coreset”): if each S i S_i S i X i X_i X i i = 1 , 2 i=1,2 i = 1 , 2 ⋃ i S i \bigcup_i S_i ⋃ i S i ⋃ i X i \bigcup_i X_i ⋃ i X i
Nevertheless, we can combine the two-pass streaming algorithm of Czumaj and Sohler [12 ] with our annular construction of a coreset to obtain a three-pass insertion-only streaming algorithm, as follows.
Corollary 1.5 (Algorithm for insertion-only streams). There is a randomized three-pass algorithm for insertion-only streams that, given as input an n n n ( X , dist ) (X,\operatorname{dist}) ( X , dist ) ddim ≥ 1 \operatorname{ddim} \ge1 ddim ≥ 1 0 < ε < 1 10 0 < \varepsilon< \frac{1}{10} 0 < ε < 10 1 OPT ^ ∈ ( 1 ± ε ) OPT ( X ) \widehat{\operatorname{OPT}} \in(1 \pm\varepsilon)\operatorname{OPT}(X) OPT ∈ ( 1 ± ε ) OPT ( X ) ( k log n ) O ( 1 ) + ( k ε ) O ( ddim ) log n (k \log n)^{O(1)} + \left(\frac{k}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n ( k log n ) O ( 1 ) + ( ε k ) O ( ddim ) log n 1 Moreover, with one additional pass, the algorithm can output a k k k X X X 1 + ε 1+\varepsilon 1 + ε
In the dynamic streaming model, the input X X X [ Δ ] d [\Delta]^d [ Δ ] d Δ = poly ( n ) \Delta=\operatorname{poly}(n) Δ = poly ( n ) O ( log n ) O(\log n) O ( log n )
Corollary 1.6 (Algorithm for dynamic Euclidean streams). There is a randomized multipass algorithm for dynamic streams that, given as input an n n n X ⊆ [ Δ ] d X \subseteq[\Delta]^d X ⊆ [ Δ ] d Δ = poly ( n ) \Delta=\operatorname{poly}(n) Δ = poly ( n ) ddim ≥ 1 \operatorname{ddim} \ge1 ddim ≥ 1 0 < ε < 1 10 0 < \varepsilon< \frac{1}{10} 0 < ε < 10 1 3 / 4 3/4 3/4 OPT ^ ∈ ( 1 ± ε ) OPT ( X ) \widehat{\operatorname{OPT}} \in(1\pm\varepsilon)\operatorname{OPT}(X) OPT ∈ ( 1 ± ε ) OPT ( X ) O ( log n ) O(\log n) O ( log n ) ( k t ε ) t log n + poly ( d , k , t , log log ( n Δ ) ) \left(\frac{kt}{\varepsilon}\right)^t \log n+\operatorname{poly}(d,k,t,\log\log(n\Delta)) ( ε k t ) t log n + poly ( d , k , t , log log ( n Δ )) t = O ( ε − 2 ( ddim log ( 1 / ε ) + log k + log log n ) ) t=O\left(\varepsilon^{-2}(\operatorname{ddim}\log(1/\varepsilon)+\log k+\log\log n)\right) t = O ( ε − 2 ( ddim log ( 1/ ε ) + log k + log log n ) ) k k k X X X 1 + ε 1+\varepsilon 1 + ε
Related Work
The min-sum k k k O ( log n ) O(\log n) O ( log n ) [8 ] , and there is also an O ( 1 ) O(1) O ( 1 ) [5 ] . Improved approximations are known for specific families of metric spaces, such as doubling metrics and planar graphs [39 ] , for small k k k k = o ( log n / log log n ) k = o(\log n/\log\log n) k = o ( log n / log log n ) [12 ] , and also for combinations thereof [42 , 32 ] .
In [12 ] there are also other types of algorithms, including sublinear-time approximation algorithm (when the input n n n n 2 n^2 n 2
The Johnson–Lindenstrauss lemma [30 ] has motivated a line of research on dimension reduction for Euclidean clustering problems. For some problems, preserving all pairwise distances among the input points immediately implies that the clustering objective value is preserved (e.g., min-sum k k k k k k k k k n n n k k k k k k [6 , 10 , 3 , 36 ] , discrete k k k k k k [29 ] , k k k [28 ] , facility location and minimum-weight spanning tree [40 , 21 ] , and more [33 , 27 , 24 , 13 GJK+25] .
Dimension reduction with additive-error guarantees has also been studied for Euclidean sets of bounded doubling dimension [26 , 1 ] . For applications of dimension reduction beyond clustering, see [15 ] .
Coresets and related streaming algorithms clustering problems have been studied extensively. Har-Peled and Mazumdar [22 ] gave one of the early coreset constructions for Euclidean k k k k k k [4 ] gave a coreset construction for balanced k k k k k k k k k k k k k k k
Yet another method for constructing coresets, that is clearly not movement-based, relies on sampling points [11 , 16 ] , and extensive subsequent work has improved and refined these methods, producing fantastic coresets for these clustering problems and many other problems. While this literature is too vast to list explicitly, we point out that it includes streaming algorithms for high-dimensional k k k k k k [7 , 25 ] .
Technical Overview
We first describe the dimension-reduction argument. Since a Gaussian JL map f f f f f f n n n 1 ± ε 1 \pm\varepsilon 1 ± ε [36 ] implies that inside any set of points (think of it as a possible cluster), one can find a small set of vertices to remove, such that the remaining subgraph has small maximum degree. This sparsity is enough for min-sum k k k
The main difficulty is to bound pairs that involve removed points, as these are not controlled by the sparse-graph argument. The key idea is to fix a reference partition, and use it to replace the contribution of such pairs with quantities that are stable under the map f f f
In the doubling-dimension theorem, this is implemented by fixing an optimal partition and considering the 1 1 1 k k k 1 1 1
For the aspect-ratio theorem, we use the same principle but now the reference partition is one whose clusters have roughly the same size, and the bounded aspect ratio is used (in the analysis) to find such a partition whose cost is not much bigger than the optimal cost. Each pair with a removed endpoint is now replaced by the average distance between the two corresponding reference clusters. Along the way, we use a known property of a Gaussian JL map f f f f f f
The two lower bounds are based on a common principle: If a Gaussian JL map f f f f f f
Now, for the Ω ( d d i m ) \Omega(\mathrm{ddim}) Ω ( ddim ) Ω ( log log n ) \Omega(\log\log n) Ω ( log log n )
We proceed to describe our two movement-based coresets. The annular construction runs in near-linear time, however its size is ( k / ε ) O ( d d i m ) log n (k/\varepsilon)^{O(\mathrm{ddim})}\log n ( k / ε ) O ( ddim ) log n k k k
This annular construction adapts the discretization approach that Har-Peled and Mazumdar [22 ] devised for a k k k
It first finds an O ( 1 ) O(1) O ( 1 ) k k k k k k ε \varepsilon ε ε / k \varepsilon/k ε / k ε \varepsilon ε ( k / ε ) O ( d d i m ) log n (k/\varepsilon)^{O(\mathrm{ddim})}\log n ( k / ε ) O ( ddim ) log n k k k
Our main coreset contribution is the density-adaptive construction that avoids the term k O ( d d i m ) k^{O(\mathrm{ddim})} k O ( ddim ) O P T ^ \widehat{\mathrm{OPT}} OPT
For each point x ∈ X x \in X x ∈ X
ρ ( x ) = min 2 ≤ m ≤ n max { 1 m ∑ v ∈ Γ m ( x ) dist ( x , v ) , O P T ^ k m 2 } . \rho(x) = \min_{2 \le m \le n} \max\left\{ \frac{1}{m} \sum_{v \in\Gamma_m(x)} \operatorname{dist}(x,v), \frac{\widehat{\mathrm{OPT}}}{km^2} \right\}. ρ ( x ) = 2 ≤ m ≤ n min max ⎩ ⎨ ⎧ m 1 v ∈ Γ m ( x ) ∑ dist ( x , v ) , k m 2 OPT ⎭ ⎬ ⎫ . where Γ m ( x ) \Gamma_m(x) Γ m ( x ) m m m x x x ρ ( x ) \rho(x) ρ ( x ) x x x O P T ^ / ( k m 2 ) \widehat{\mathrm{OPT}}/(km^2) OPT / ( k m 2 ) m m m m m m m 2 m^2 m 2 O ( O P T ^ / k ) O(\widehat{\mathrm{OPT}}/k) O ( OPT / k )
Our coreset algorithm group points x ∈ X x \in X x ∈ X ρ ( x ) \rho(x) ρ ( x ) ρ ( x ) \rho(x) ρ ( x ) ρ ( x ) \rho(x) ρ ( x )
Conclusions
Our dimension-reduction and coreset results preserve substantially more than the optimal clustering value. In particular, our movement-based coreset maps the points to representatives such that the costs of all k k k
This motivates a weaker notion focused on preserving the optimum. We call a weighted subset ( S , w ) (S,w) ( S , w ) ε \varepsilon ε k k k X X X
OPT ( S , w ) ∈ ( 1 ± ε ) OPT ( X ) , \operatorname{OPT}(S,w) \in(1 \pm\varepsilon)\operatorname{OPT}(X), OPT ( S , w ) ∈ ( 1 ± ε ) OPT ( X ) , and there exists a polynomial-time algorithm that converts every γ \gamma γ ( S , w ) (S,w) ( S , w ) γ ( 1 + ε ) \gamma(1+\varepsilon) γ ( 1 + ε ) X X X
We don’t know whether this weaker notion admits smaller coresets, particularly with improved dependence on n n n k k k k k k k k k
Preliminaries
Nets and Doubling Metrics
Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) x ∈ X x \in X x ∈ X r > 0 r > 0 r > 0 B X ( x , r ) = { y ∈ X : dist ( x , y ) ≤ r } B_X(x,r) = \{y \in X : \operatorname{dist}(x,y) \le r\} B X ( x , r ) = { y ∈ X : dist ( x , y ) ≤ r } X X X
Definition 2.1 (r r r ( X , dist ) (X,\operatorname{dist}) ( X , dist ) r > 0 r > 0 r > 0 N ⊆ X N \subseteq X N ⊆ X r r r
∀ u ≠ v ∈ N , dist ( u , v ) > r . \forall u \ne v \in N,\qquad\operatorname{dist}(u,v) > r. ∀ u = v ∈ N , dist ( u , v ) > r . A subset N ⊆ X N \subseteq X N ⊆ X r r r X X X
∀ x ∈ X , ∃ u ∈ N , such that x ∈ B X ( u , r ) . \forall x \in X,\exists u \in N,\text{ such that }x \in B_X(u,r). ∀ x ∈ X , ∃ u ∈ N , such that x ∈ B X ( u , r ) . A subset N ⊆ X N \subseteq X N ⊆ X r r r X X X r r r r r r X X X
Lemma 2.2 (Packing Property [19 Proposition 1.1] ). Let P P P N ⊆ P N \subseteq P N ⊆ P r r r
∣ N ∣ ≤ ( diam ( P ) r ) O ( ddim ( P ) ) . |N| \le\left(\frac{\operatorname{diam}(P)}{r}\right)^{O(\operatorname{ddim}(P))}. ∣ N ∣ ≤ ( r diam ( P ) ) O ( ddim ( P )) . Gaussian JL Maps
Definition 2.3 (Random Dimension Reduction). A random map f : R d → R t f:\mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) X X X
∀ A , B ⊆ X , Pr [ ∑ x ∈ A , y ∈ B ∥ f ( x ) − f ( y ) ∥ ∈ ( 1 ± ε ) ∑ x ∈ A , y ∈ B ∥ x − y ∥ ] ≥ 1 − δ . \forall A,B \subseteq X,\qquad\Pr\left[\sum_{x\in A,y\in B}\|f(x)-f(y)\| \in(1\pm\varepsilon)\sum_{x\in A,y\in B}\|x-y\|\right] \ge1-\delta. ∀ A , B ⊆ X , Pr x ∈ A , y ∈ B ∑ ∥ f ( x ) − f ( y ) ∥ ∈ ( 1 ± ε ) x ∈ A , y ∈ B ∑ ∥ x − y ∥ ≥ 1 − δ . It is called an ( ε , δ , ρ ) (\varepsilon,\delta,\rho) ( ε , δ , ρ ) X X X
∀ x , y ∈ X , E [ max { 0 , ∥ f ( x ) − f ( y ) ∥ − ( 1 + ε ) ∥ x − y ∥ } ] ≤ ρ ∥ x − y ∥ . \forall x,y\in X,\qquad\mathbb{E}\left[\max\{0,\|f(x)-f(y)\|-(1+\varepsilon)\|x-y\|\}\right]\le\rho\|x-y\|. ∀ x , y ∈ X , E [ max { 0 , ∥ f ( x ) − f ( y ) ∥ − ( 1 + ε ) ∥ x − y ∥ } ] ≤ ρ ∥ x − y ∥. Definition 2.4 (Local Ball-Tail Property). Let f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t f f f μ \mu μ X X X
∀ y ∈ X , r > 0 , Pr [ ∃ x ∈ X ∩ B ( y , r ) , ∥ f ( x ) − f ( y ) ∥ ≥ 10 r ] ≤ e − μ . \forall y\in X,\ r>0,\qquad\Pr\left[\exists x\in X\cap B(y,r),\ \|f(x)-f(y)\|\ge10r\right]\le e^{-\mu}. ∀ y ∈ X , r > 0 , Pr [ ∃ x ∈ X ∩ B ( y , r ) , ∥ f ( x ) − f ( y ) ∥ ≥ 10 r ] ≤ e − μ . Lemma 2.5 (Gaussian Pair Tail [Mat08, Theorem 3.1]). There is a universal constant c > 0 c>0 c > 0 0 < ε , δ < 1 0<\varepsilon,\delta<1 0 < ε , δ < 1 f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 log ( 1 / δ ) t\ge c\varepsilon^{-2}\log(1/\delta) t ≥ c ε − 2 log ( 1/ δ ) x , y ∈ R d x,y\in\mathbb{R}^{d} x , y ∈ R d
Pr [ ∥ f ( x ) − f ( y ) ∥ ∉ ( 1 ± ε ) ∥ x − y ∥ ] ≤ δ . \Pr[\|f(x)-f(y)\|\notin(1\pm\varepsilon)\|x-y\|]\le\delta. Pr [ ∥ f ( x ) − f ( y ) ∥ ∈ / ( 1 ± ε ) ∥ x − y ∥ ] ≤ δ . Lemma 2.6 (Gaussian Set-Pair Preservation [Dan21, Subsection A.1]). There is a universal constant c > 0 c>0 c > 0 0 < ε , δ < 1 0<\varepsilon,\delta<1 0 < ε , δ < 1 X ⊆ R d X\subseteq\mathbb{R}^{d} X ⊆ R d f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 ( log ( 1 / ε ) + log ( 1 / δ ) ) t\ge c\varepsilon^{-2}(\log(1/\varepsilon)+\log(1/\delta)) t ≥ c ε − 2 ( log ( 1/ ε ) + log ( 1/ δ )) f f f ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) X X X
Lemma 2.7 (Gaussian One-Sided Excess [36 Lemmas C.1 and C.2] ). There is a universal constant c > 0 c>0 c > 0 0 < ε , ρ < 1 0<\varepsilon,\rho<1 0 < ε , ρ < 1 f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 ( log ( 1 / ε ) + log ( 1 / ρ ) ) t\ge c\varepsilon^{-2}(\log(1/\varepsilon)+\log(1/\rho)) t ≥ c ε − 2 ( log ( 1/ ε ) + log ( 1/ ρ ))
∀ x , y ∈ R d , E [ max { 0 , ∥ f ( x ) − f ( y ) ∥ − ( 1 + ε ) ∥ x − y ∥ } ] ≤ ρ ∥ x − y ∥ . \forall x,y\in\mathbb{R}^{d},\qquad\mathbb{E}\left[\max\{0,\|f(x)-f(y)\|-(1+\varepsilon)\|x-y\|\}\right]\le\rho\|x-y\|. ∀ x , y ∈ R d , E [ max { 0 , ∥ f ( x ) − f ( y ) ∥ − ( 1 + ε ) ∥ x − y ∥ } ] ≤ ρ ∥ x − y ∥. Lemma 2.8 (Gaussian Local Ball-Tail in Doubling Sets [26 ] ). There is a universal constant c > 0 c>0 c > 0 X ⊆ R d X\subseteq\mathbb{R}^{d} X ⊆ R d ddim ≥ 1 \operatorname{ddim}\ge1 ddim ≥ 1 f : R d → R t f:\mathbb{R}^{d}\to\mathbb{R}^{t} f : R d → R t t ≥ c ( ddim + μ ) t\ge c(\operatorname{ddim}+\mu) t ≥ c ( ddim + μ ) f f f μ \mu μ X X X
Dimension Reduction for Min-Sum k k k
In this section we prove two dimension-reduction theorems, stated below for convenience. The first depends on the doubling dimension of the data, and the second depends on the aspect ratio.
Theorem 1.2 (Euclidean Dimension Reduction for Doubling Sets). Let X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d min-sum k k k in Euclidean space, and let 0 < ε < 1 / 4 0 < \varepsilon< 1/4 0 < ε < 1/4 f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 ( ddim ( X ) log ( 1 / ε ) + log k + log log n ) t \ge c\varepsilon^{-2}\left(\operatorname{ddim}(X)\log(1/\varepsilon) + \log k + \log\log n\right) t ≥ c ε − 2 ( ddim ( X ) log ( 1/ ε ) + log k + log log n ) c > 0 c > 0 c > 0 4 / 5 4/5 4/5
∀ k -partition P of X , cost ( f ( P ) ) ∈ ( 1 ± ε ) cost ( P ) . \forall k\text{-partition } P \text{ of } X,\qquad\operatorname{cost}(f(P)) \in(1 \pm\varepsilon)\operatorname{cost}(P). ∀ k -partition P of X , cost ( f ( P )) ∈ ( 1 ± ε ) cost ( P ) . Theorem 1.3 (Euclidean Dimension Reduction for Bounded Aspect Ratio). Let X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d min-sum k k k in Euclidean space with aspect ratio at most Δ \Delta Δ 0 < ε < 1 / 4 0 < \varepsilon< 1/4 0 < ε < 1/4 f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t t ≥ c ε − 2 ( log ( 1 / ε ) + log k + log Δ ) t \ge c\varepsilon^{-2}\left(\log(1/\varepsilon) + \log k + \log\Delta\right) t ≥ c ε − 2 ( log ( 1/ ε ) + log k + log Δ ) c > 0 c > 0 c > 0 4 / 5 4/5 4/5
∀ k -partition P of X , cost ( f ( P ) ) ∈ ( 1 ± ε ) cost ( P ) . \forall k\text{-partition } P \text{ of } X,\qquad\operatorname{cost}(f(P)) \in(1 \pm\varepsilon)\operatorname{cost}(P). ∀ k -partition P of X , cost ( f ( P )) ∈ ( 1 ± ε ) cost ( P ) . Preliminaries: Distortion Graph and Related Tools
Both dimension-reduction upper bounds rely on an intermediate guarantee, which shows that even after the map f f f C ⊆ X C \subseteq X C ⊆ X f f f
Definition 3.1 (Distortion graph). Given 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2 distortion graph G = ( X , E ) G = (X, E) G = ( X , E ) f f f X X X ( x , y ) ∈ E (x,y) \in E ( x , y ) ∈ E
∥ f ( x ) − f ( y ) ∥ ∉ ( 1 ± ε ) ∥ x − y ∥ . \lVert f(x) - f(y) \rVert\notin(1 \pm\varepsilon)\lVert x-y\rVert. ∥ f ( x ) − f ( y )∥ ∈ / ( 1 ± ε ) ∥ x − y ∥ . Observe that when f f f ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) X X X
∀ x , y ∈ X , Pr [ ( x , y ) ∈ E ] ≤ δ . \forall x,y \in X,\qquad\Pr[(x,y) \in E] \le\delta. ∀ x , y ∈ X , Pr [( x , y ) ∈ E ] ≤ δ . Definition 3.2 (Everywhere-sparse graph). A graph H = ( V , E ) H = (V, E) H = ( V , E ) θ \theta θ everywhere sparse if
∀ u ∈ V , deg H ( u ) ≤ θ ∣ V ∣ . \forall u \in V,\qquad\deg_{H}(u) \le\theta|V|. ∀ u ∈ V , deg H ( u ) ≤ θ ∣ V ∣. Notice that this definition allows V V V
Theorem 3.3 (Sparse Subgraph Theorem [36 Theorem 3.2] ). Consider a finite set X X X H = ( V , E ) H = (V, E) H = ( V , E ) V V V X X X E E E V V V θ ∈ ( 0 , 1 / 2 ) \theta\in(0,1/2) θ ∈ ( 0 , 1/2 )
∀ x , y ∈ X , Pr [ ( x , y ) ∈ E ] ≤ δ , \forall x,y \in X,\qquad\Pr[(x,y) \in E] \le\delta, ∀ x , y ∈ X , Pr [( x , y ) ∈ E ] ≤ δ , where δ ≤ θ 7 / 600 \delta\le\theta^{7}/600 δ ≤ θ 7 /600 V ′ ⊆ V V' \subseteq V V ′ ⊆ V
H [ V ′ ] H[V'] H [ V ′ ] θ \theta θ
Pr [ u ∈ V ∖ V ′ ] ≤ θ \Pr[u \in V \setminus V'] \le\theta Pr [ u ∈ V ∖ V ′ ] ≤ θ u ∈ X u \in X u ∈ X
:::`
Lemma 3.4 (Sparse Graph Preservation). Let θ ≤ 1 / 10 \theta\le1/10 θ ≤ 1/10 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2 G = ( Y , E ) G = (Y,E) G = ( Y , E ) Y Y Y f f f G G G θ \theta θ
∑ x , y ∈ Y ∥ f ( x ) − f ( y ) ∥ ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) ∑ x , y ∈ Y ∥ x − y ∥ . (2) \sum_{x,y\in Y} \lVert f(x)-f(y)\rVert\le(1+5\theta)(1+2\varepsilon)\sum_{x,y\in Y}\lVert x-y\rVert. \tag*{(2)} x , y ∈ Y ∑ ∥ f ( x ) − f ( y )∥ ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) x , y ∈ Y ∑ ∥ x − y ∥ . (2) and
∑ x , y ∈ Y ∥ x − y ∥ ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) ∑ x , y ∈ Y ∥ f ( x ) − f ( y ) ∥ . (3) \sum_{x,y\in Y}\lVert x-y\rVert\le(1+5\theta)(1+2\varepsilon)\sum_{x,y\in Y}\lVert f(x)-f(y)\rVert. \tag*{(3)} x , y ∈ Y ∑ ∥ x − y ∥ ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) x , y ∈ Y ∑ ∥ f ( x ) − f ( y )∥ . (3) Proof. For each x ∈ Y x\in Y x ∈ Y I x = { y ∈ Y : ( x , y ) ∉ E } I_x=\{y\in Y:(x,y)\notin E\} I x = { y ∈ Y : ( x , y ) ∈ / E } G G G θ \theta θ
∀ x , y ∈ Y , ∣ I x ∩ I y ∣ ≥ ( 1 − 2 θ ) ∣ Y ∣ . \forall x,y\in Y,\qquad|I_x\cap I_y|\ge(1-2\theta)|Y|. ∀ x , y ∈ Y , ∣ I x ∩ I y ∣ ≥ ( 1 − 2 θ ) ∣ Y ∣. Now fix x , y ∈ X x,y\in X x , y ∈ X z ∈ I x ∩ I y z\in I_x\cap I_y z ∈ I x ∩ I y
∥ f ( x ) − f ( y ) ∥ ≤ ∥ f ( x ) − f ( z ) ∥ + ∥ f ( z ) − f ( y ) ∥ ≤ ( 1 + ε ) ( ∥ x − z ∥ + ∥ z − y ∥ ) , \lVert f(x)-f(y)\rVert\le\lVert f(x)-f(z)\rVert+\lVert f(z)-f(y)\rVert\le(1+\varepsilon)(\lVert x-z\rVert+\lVert z-y\rVert), ∥ f ( x ) − f ( y )∥ ≤ ∥ f ( x ) − f ( z )∥ + ∥ f ( z ) − f ( y )∥ ≤ ( 1 + ε ) (∥ x − z ∥ + ∥ z − y ∥) , and averaging this over all z ∈ I x ∩ I y z\in I_x\cap I_y z ∈ I x ∩ I y
∥ f ( x ) − f ( y ) ∥ ≤ 1 + ε ( 1 − 2 θ ) ∣ Y ∣ ∑ z ∈ I x ∩ I y ( ∥ x − z ∥ + ∥ z − y ∥ ) . \lVert f(x)-f(y)\rVert\le\frac{1+\varepsilon}{(1-2\theta)|Y|}\sum_{z\in I_x\cap I_y}(\lVert x-z\rVert+\lVert z-y\rVert). ∥ f ( x ) − f ( y )∥ ≤ ( 1 − 2 θ ) ∣ Y ∣ 1 + ε z ∈ I x ∩ I y ∑ (∥ x − z ∥ + ∥ z − y ∥) . Now split the sum ∑ x , y ∈ X ∥ f ( x ) − f ( y ) ∥ \sum_{x,y\in X}\lVert f(x)-f(y)\rVert ∑ x , y ∈ X ∥ f ( x ) − f ( y )∥ ( 1 + ε ) ∑ x , y ∈ Y ∥ x − y ∥ (1+\varepsilon)\sum_{x,y\in Y}\lVert x-y\rVert ( 1 + ε ) ∑ x , y ∈ Y ∥ x − y ∥ 4 θ ∣ Y ∣ 4\theta|Y| 4 θ ∣ Y ∣
∑ x , y ∈ Y , y ∉ I x ∥ f ( x ) − f ( y ) ∥ ≤ ( 1 + ε ) 4 θ 1 − 2 θ ∑ x , y ∈ Y , y ∈ I x ∥ x − y ∥ ≤ 5 θ ( 1 + ε ) ∑ x , y ∈ Y ∥ x − y ∥ . (4) \sum_{x,y\in Y,y\notin I_x}\lVert f(x)-f(y)\rVert\le(1+\varepsilon)\frac{4\theta}{1-2\theta}\sum_{x,y\in Y,y\in I_x}\lVert x-y\rVert\le5\theta(1+\varepsilon)\sum_{x,y\in Y}\lVert x-y\rVert. \tag*{(4)} x , y ∈ Y , y ∈ / I x ∑ ∥ f ( x ) − f ( y )∥ ≤ ( 1 + ε ) 1 − 2 θ 4 θ x , y ∈ Y , y ∈ I x ∑ ∥ x − y ∥ ≤ 5 θ ( 1 + ε ) x , y ∈ Y ∑ ∥ x − y ∥ . (4) where the second inequality follows from θ ≤ 1 / 10 \theta\le1/10 θ ≤ 1/10 (4) together with the bound on the distorted pairs contribution proves (2) . Inequality (3) follows in the same way, using
z ∈ I x ∩ I y , ∥ x − y ∥ ≤ 1 1 − ε ( ∥ f ( x ) − f ( z ) ∥ + ∥ f ( z ) − f ( y ) ∥ ) , z\in I_x\cap I_y,\qquad\lVert x-y\rVert\le\frac{1}{1-\varepsilon}(\lVert f(x)-f(z)\rVert+\lVert f(z)-f(y)\rVert), z ∈ I x ∩ I y , ∥ x − y ∥ ≤ 1 − ε 1 (∥ f ( x ) − f ( z )∥ + ∥ f ( z ) − f ( y )∥) , and the conclusion follows from 1 / ( 1 − ε ) ≤ 1 + 2 ε 1/(1-\varepsilon)\le1+2\varepsilon 1/ ( 1 − ε ) ≤ 1 + 2 ε
Lemma 3.5 (One-Median Charge). Let S ⊆ R d S\subseteq\mathbb{R}^d S ⊆ R d c ∗ c^* c ∗ S S S 1 1 1
∣ S ∣ ∑ y ∈ S ∥ y − c ∗ ∥ ≤ ∑ y , y ′ ∈ S ∥ y − y ′ ∥ . |S|\sum_{y\in S}\lVert y-c^*\rVert\le\sum_{y,y'\in S}\lVert y-y'\rVert. ∣ S ∣ y ∈ S ∑ ∥ y − c ∗ ∥ ≤ y , y ′ ∈ S ∑ ∥ y − y ′ ∥ . Proof. Since c ∗ c^* c ∗ S S S
∀ y ′ ∈ S , ∑ y ∈ S ∥ y − c ∗ ∥ ≤ ∑ y ∈ S ∥ y − y ′ ∥ . \forall y'\in S,\qquad\sum_{y\in S}\lVert y-c^*\rVert\le\sum_{y\in S}\lVert y-y'\rVert. ∀ y ′ ∈ S , y ∈ S ∑ ∥ y − c ∗ ∥ ≤ y ∈ S ∑ ∥ y − y ′ ∥ . Summing over all y ′ ∈ S y'\in S y ′ ∈ S
Upper Bound for Doubling Dimension
The next lemma is the core of the doubling-dimension argument. It shows that for every random subset C ⊆ X C \subseteq X C ⊆ X C C C f ( C ) f(C) f ( C ) Theorem 3.3 and Lemma 3.4 to obtain a subset C ′ ⊆ C C' \subseteq C C ′ ⊆ C C ′ C' C ′ cost ( C ) \operatorname{cost}(C) cost ( C ) OPT \operatorname{OPT} OPT
Lemma 3.6 (Preservation of a Random Cluster). Let X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d k k k ddim ≥ 1 \operatorname{ddim} \ge1 ddim ≥ 1 P ∗ = { P 1 ∗ , … , P k ∗ } P^{*} = \{P_{1}^{*}, \ldots, P_{k}^{*}\} P ∗ = { P 1 ∗ , … , P k ∗ } X X X OPT = cost ( P ∗ ) \operatorname{OPT} = \operatorname{cost}(P^{*}) OPT = cost ( P ∗ ) 0 < ε ≤ 1 / 2 0 < \varepsilon\le1/2 0 < ε ≤ 1/2
θ ≤ 1 20 , δ ≤ min { θ 7 600 , ε α ddim 100 k 2 log 2 n } , μ ≥ β ( ddim log ( 1 / ε ) + log k + log log n ) . \theta\le\frac{1}{20}, \qquad\delta\le\min\left\{\frac{\theta^{7}}{600}, \frac{\varepsilon^{\alpha\operatorname{ddim}}}{100k^{2}\log^{2}n}\right\}, \qquad\mu\ge\beta\bigl(\operatorname{ddim}\log(1/\varepsilon)+\log k+\log\log n\bigr). θ ≤ 20 1 , δ ≤ min { 600 θ 7 , 100 k 2 log 2 n ε α ddim } , μ ≥ β ( ddim log ( 1/ ε ) + log k + log log n ) . for sufficiently large constants α , β > 0 \alpha,\beta> 0 α , β > 0 f : R d → R t f : \mathbb{R}^{d} \to\mathbb{R}^{t} f : R d → R t
∀ x , y ∈ X , Pr [ ∥ f ( x ) − f ( y ) ∥ ∉ ( 1 ± ε ) ∥ x − y ∥ ] ≤ δ , \forall x,y \in X,\qquad\Pr[\lVert f(x)-f(y)\rVert\notin(1\pm\varepsilon)\lVert x-y\rVert]\le\delta, ∀ x , y ∈ X , Pr [∥ f ( x ) − f ( y )∥ ∈ / ( 1 ± ε ) ∥ x − y ∥] ≤ δ , and assume that f f f μ \mu μ X X X C ⊆ X C \subseteq X C ⊆ X f f f 4 / 5 4/5 4/5
cost ( C ) ≤ A ( cost ( f ( C ) ) + O ( ε ( k θ + n − 8 ) OPT ) ) , (5) \operatorname{cost}(C)\le A\bigl(\operatorname{cost}(f(C))+O(\varepsilon(k\theta+n^{-8})\operatorname{OPT})\bigr), \tag*{(5)} cost ( C ) ≤ A ( cost ( f ( C )) + O ( ε ( k θ + n − 8 ) OPT ) ) , (5) cost ( f ( C ) ) ≤ A ( cost ( C ) + O ( ε ( k θ + n − 8 ) OPT ) ) , (6) \operatorname{cost}(f(C))\le A\bigl(\operatorname{cost}(C)+O(\varepsilon(k\theta+n^{-8})\operatorname{OPT})\bigr), \tag*{(6)} cost ( f ( C )) ≤ A ( cost ( C ) + O ( ε ( k θ + n − 8 ) OPT ) ) , (6) where A = ( 1 + 5 θ ) ( 1 + 2 ε ) A=(1+5\theta)(1+2\varepsilon) A = ( 1 + 5 θ ) ( 1 + 2 ε )
Proof. Let c j ∗ c_j^* c j ∗ P j ∗ P_j^* P j ∗ r 0 = 20 OPT r_0=20\operatorname{OPT} r 0 = 20 OPT m 0 = O ( log n ) m_0=O(\log n) m 0 = O ( log n ) 2 m 0 = 40 n 10 2^{m_0}=40n^{10} 2 m 0 = 40 n 10 i = 0 , … , m 0 i=0,\ldots,m_0 i = 0 , … , m 0 r i = r 0 / 2 i r_i=r_0/2^i r i = r 0 / 2 i N i j N_{ij} N ij ( ε r i / 100 ) (\varepsilon r_i/100) ( ε r i /100 ) X ∩ B ( c j ∗ , r i ) X\cap B(c_j^*,r_i) X ∩ B ( c j ∗ , r i )
N = ⋃ i = 0 m 0 ⋃ j = 1 k N i j . N=\bigcup_{i=0}^{m_0}\bigcup_{j=1}^{k}N_{ij}. N = i = 0 ⋃ m 0 j = 1 ⋃ k N ij . By Lemma 2.2 , applied to each N i j N_{ij} N ij
∣ N ∣ ≤ k ε − O ( ddim ) log n . |N|\le k\varepsilon^{-O(\operatorname{ddim})}\log n. ∣ N ∣ ≤ k ε − O ( ddim ) log n . Using the pairwise distortion assumption and taking a union bound over N × N N\times N N × N
Pr [ ∃ u , v ∈ N , ∥ f ( u ) − f ( v ) ∥ ∉ ( 1 ± ε ) ∥ u − v ∥ ] ≤ δ ∣ N ∣ 2 ≤ 1 100 . (7) \Pr\left[\exists u,v\in N,\ \lVert f(u)-f(v)\rVert\notin(1\pm\varepsilon)\lVert u-v\rVert\right]\le\delta|N|^{2}\le\frac{1}{100}. \tag*{(7)} Pr [ ∃ u , v ∈ N , ∥ f ( u ) − f ( v )∥ ∈ / ( 1 ± ε ) ∥ u − v ∥ ] ≤ δ ∣ N ∣ 2 ≤ 100 1 . (7) Additionally, since f f f μ \mu μ i , j i,j i , j y ∈ N i j y\in N_{ij} y ∈ N ij
Pr [ ∃ x ∈ X ∩ B ( y , ε r i / 100 ) , ∥ f ( x ) − f ( y ) ∥ > ε r i / 10 ] ≤ e − μ . \Pr\left[\exists x\in X\cap B(y,\varepsilon r_i/100),\ \lVert f(x)-f(y)\rVert>\varepsilon r_i/10\right]\le e^{-\mu}. Pr [ ∃ x ∈ X ∩ B ( y , ε r i /100 ) , ∥ f ( x ) − f ( y )∥ > ε r i /10 ] ≤ e − μ . For a sufficiently large constant β \beta β
Pr [ ∃ i , j , y ∈ N i j , ∃ x ∈ X ∩ B ( y , ε r i / 100 ) , ∥ f ( x ) − f ( y ) ∥ > ε r i / 10 ] ≤ 1 100 . (8) \Pr\left[\exists i,j,y\in N_{ij},\ \exists x\in X\cap B(y,\varepsilon r_i/100),\ \lVert f(x)-f(y)\rVert>\varepsilon r_i/10\right]\le\frac{1}{100}. \tag*{(8)} Pr [ ∃ i , j , y ∈ N ij , ∃ x ∈ X ∩ B ( y , ε r i /100 ) , ∥ f ( x ) − f ( y )∥ > ε r i /10 ] ≤ 100 1 . (8) Let Λ \Lambda Λ (7) nor (8) occurs. Then Pr ( Λ ) ≥ 9 / 10 \Pr(\Lambda) \ge9/10 Pr ( Λ ) ≥ 9/10 C C C X X X G [ C ] G[C] G [ C ] C C C Theorem 3.3 , there exists C ′ ⊆ C C' \subseteq C C ′ ⊆ C G [ C ′ ] G[C'] G [ C ′ ] θ \theta θ
∀ u ∈ X , Pr [ u ∈ C ∖ C ′ ] ≤ θ . \forall u \in X,\qquad\Pr[u \in C \setminus C'] \le\theta. ∀ u ∈ X , Pr [ u ∈ C ∖ C ′ ] ≤ θ . Consider a pair x , y ∈ C x,y \in C x , y ∈ C y ∈ P ℓ ∗ y \in P^*_\ell y ∈ P ℓ ∗ x ∈ P j ∗ x \in P^*_j x ∈ P j ∗ ∣ P ℓ ∗ ∣ ≥ ∣ P j ∗ ∣ |P^*_\ell| \ge|P^*_j| ∣ P ℓ ∗ ∣ ≥ ∣ P j ∗ ∣ r ( x , y ) > 0 r(x,y)>0 r ( x , y ) > 0 u ( x , y ) ∈ N u(x,y) \in N u ( x , y ) ∈ N ∥ x − y ∥ ≤ 2 OPT \|x-y\| \le2\operatorname{OPT} ∥ x − y ∥ ≤ 2 OPT r ( x , y ) r(x,y) r ( x , y ) r i r_i r i
∥ x − c ℓ ∗ ∥ ≤ r i , \|x-c^*_\ell\| \le r_i, ∥ x − c ℓ ∗ ∥ ≤ r i , and let u ( x , y ) u(x,y) u ( x , y ) x x x N i ℓ N_{i\ell} N i ℓ r ( x , y ) = r 0 r(x,y)=r_0 r ( x , y ) = r 0 u ( x , y ) u(x,y) u ( x , y ) x x x N 0 j N_{0j} N 0 j ∥ x − y ∥ > 2 OPT \|x-y\|>2\operatorname{OPT} ∥ x − y ∥ > 2 OPT ∥ y − c ℓ ∗ ∥ ≤ OPT \|y-c^*_\ell\|\le\operatorname{OPT} ∥ y − c ℓ ∗ ∥ ≤ OPT ∥ x − c ℓ ∗ ∥ > OPT \|x-c^*_\ell\|>\operatorname{OPT} ∥ x − c ℓ ∗ ∥ > OPT r ( y , x ) r(y,x) r ( y , x ) u ( y , x ) u(y,x) u ( y , x ) y y y c ℓ ∗ c^*_\ell c ℓ ∗ r ( y , x ) r(y,x) r ( y , x ) ∥ y − c ℓ ∗ ∥ ≤ r i \|y-c^*_\ell\|\le r_i ∥ y − c ℓ ∗ ∥ ≤ r i u ( y , x ) u(y,x) u ( y , x ) y y y
r ( x , y ) ≤ max { 25 ∥ x − c ℓ ∗ ∥ , OPT 2 n 10 } , r ( y , x ) ≤ max { 2 ∥ y − c ℓ ∗ ∥ , OPT 2 n 10 } . (9) r(x,y) \le\max\left\{25\|x-c^*_\ell\|,\frac{\operatorname{OPT}}{2n^{10}}\right\},\qquad
r(y,x) \le\max\left\{2\|y-c^*_\ell\|,\frac{\operatorname{OPT}}{2n^{10}}\right\}. \tag*{(9)} r ( x , y ) ≤ max { 25∥ x − c ℓ ∗ ∥ , 2 n 10 OPT } , r ( y , x ) ≤ max { 2∥ y − c ℓ ∗ ∥ , 2 n 10 OPT } . (9) Thus
r ( x , y ) + r ( y , x ) ≤ OPT n 10 + 25 ∥ x − c ℓ ∗ ∥ + 2 ∥ y − c ℓ ∗ ∥ ≤ OPT n 10 + 25 ∥ x − y ∥ + 30 ∥ y − c ℓ ∗ ∥ . (10) \begin{aligned}
r(x,y)+r(y,x)
&\le\frac{\operatorname{OPT}}{n^{10}}+25\|x-c^*_\ell\|+2\|y-c^*_\ell\| \\
&\le\frac{\operatorname{OPT}}{n^{10}}+25\|x-y\|+30\|y-c^*_\ell\|. \tag*{(10)}
\end{aligned} r ( x , y ) + r ( y , x ) ≤ n 10 OPT + 25∥ x − c ℓ ∗ ∥ + 2∥ y − c ℓ ∗ ∥ ≤ n 10 OPT + 25∥ x − y ∥ + 30∥ y − c ℓ ∗ ∥. (10) Therefore
∣ ∥ x − y ∥ − ∥ u ( x , y ) − u ( y , x ) ∥ ∣ ≤ ∥ x − u ( x , y ) ∥ + ∥ y − u ( y , x ) ∥ ≤ ε 100 ( r ( x , y ) + r ( y , x ) ) ≤ ε ( OPT n 10 + ∥ x − y ∥ 4 + 3 ∥ y − c ℓ ∗ ∥ 10 ) . (11) \begin{aligned}
\left|\|x-y\|-\|u(x,y)-u(y,x)\|\right|
&\le\|x-u(x,y)\|+\|y-u(y,x)\| \\
&\le\frac{\varepsilon}{100}\left(r(x,y)+r(y,x)\right) \\
&\le\varepsilon\left(\frac{\operatorname{OPT}}{n^{10}}+\frac{\|x-y\|}{4}+\frac{3\|y-c^*_\ell\|}{10}\right). \tag*{(11)}
\end{aligned} ∣ ∥ x − y ∥ − ∥ u ( x , y ) − u ( y , x ) ∥ ∣ ≤ ∥ x − u ( x , y ) ∥ + ∥ y − u ( y , x ) ∥ ≤ 100 ε ( r ( x , y ) + r ( y , x ) ) ≤ ε ( n 10 OPT + 4 ∥ x − y ∥ + 10 3∥ y − c ℓ ∗ ∥ ) . (11) If event Λ \Lambda Λ (8) does not occur. Hence ∥ f ( x ) − f ( u ( x , y ) ) ∥ ≤ ε r ( x , y ) / 10 \|f(x)-f(u(x,y))\|\le\varepsilon r(x,y)/10 ∥ f ( x ) − f ( u ( x , y )) ∥ ≤ ε r ( x , y ) /10 ∥ f ( y ) − f ( u ( y , x ) ) ∥ ≤ ε r ( y , x ) / 10 \|f(y)-f(u(y,x))\|\le\varepsilon r(y,x)/10 ∥ f ( y ) − f ( u ( y , x )) ∥ ≤ ε r ( y , x ) /10 (10) therefore give:
∣ ∥ f ( x ) − f ( y ) ∥ − ∥ f ( u ( x , y ) ) − f ( u ( y , x ) ) ∥ ∣ ≤ ∥ f ( x ) − f ( u ( x , y ) ) ∥ + ∥ f ( y ) − f ( u ( y , x ) ) ∥ ≤ ε 10 ( r ( x , y ) + r ( y , x ) ) ≤ ε 10 ( OPT n 10 + 25 ∥ x − y ∥ + 30 ∥ y − c ℓ ∗ ∥ ) . (12) \begin{aligned}
\left|\|f(x)-f(y)\|-\|f(u(x,y))-f(u(y,x))\|\right|
&\le\|f(x)-f(u(x,y))\|+\|f(y)-f(u(y,x))\| \\
&\le\frac{\varepsilon}{10}\left(r(x,y)+r(y,x)\right) \\
&\le\frac{\varepsilon}{10}\left(\frac{\operatorname{OPT}}{n^{10}}+25\|x-y\|+30\|y-c^*_\ell\|\right). \tag*{(12)}
\end{aligned} ∣ ∥ f ( x ) − f ( y ) ∥ − ∥ f ( u ( x , y )) − f ( u ( y , x )) ∥ ∣ ≤ ∥ f ( x ) − f ( u ( x , y )) ∥ + ∥ f ( y ) − f ( u ( y , x )) ∥ ≤ 10 ε ( r ( x , y ) + r ( y , x ) ) ≤ 10 ε ( n 10 OPT + 25∥ x − y ∥ + 30∥ y − c ℓ ∗ ∥ ) . (12) Define
g ( x , y ) = { x , x , y ∈ C ′ , u ( x , y ) , otherwise . g(x,y)=
\begin{cases}
x, & x,y\in C',\\
u(x,y), & \text{otherwise}.
\end{cases} g ( x , y ) = { x , u ( x , y ) , x , y ∈ C ′ , otherwise . Then set
cost g ( C ) = ∑ x , y ∈ C ∥ g ( x , y ) − g ( y , x ) ∥ \operatorname{cost}_g(C)=\sum_{x,y\in C}\|g(x,y)-g(y,x)\| cost g ( C ) = x , y ∈ C ∑ ∥ g ( x , y ) − g ( y , x ) ∥ and
cost g ( f ( C ) ) = ∑ x , y ∈ C ∥ f ( g ( x , y ) ) − f ( g ( y , x ) ) ∥ . \operatorname{cost}_{g}(f(C))=\sum_{x,y\in C}\left\lVert f(g(x,y))-f(g(y,x))\right\rVert. cost g ( f ( C )) = x , y ∈ C ∑ ∥ f ( g ( x , y )) − f ( g ( y , x )) ∥ . Let S = { ( x , y ) ∈ C × C : x ∉ C ′ or y ∉ C ′ } S=\{(x,y)\in C\times C:x\notin C' \text{ or } y\notin C'\} S = {( x , y ) ∈ C × C : x ∈ / C ′ or y ∈ / C ′ } Λ \Lambda Λ Lemma 3.4 on C ′ C' C ′
cost g ( f ( C ) ) ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) ∑ x , y ∈ C ′ ∥ x − y ∥ + ( 1 + ε ) ∑ ( x , y ) ∈ S ∥ u ( x , y ) − u ( y , x ) ∥ ≤ A cost g ( C ) , (13) \begin{aligned}
\operatorname{cost}_{g}(f(C))&\leq(1+5\theta)(1+2\varepsilon)\sum_{x,y\in C'}\lVert x-y\rVert+(1+\varepsilon)\sum_{(x,y)\in S}\lVert u(x,y)-u(y,x)\rVert\\
&\leq A\operatorname{cost}_{g}(C), \tag*{(13)}
\end{aligned} cost g ( f ( C )) ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) x , y ∈ C ′ ∑ ∥ x − y ∥ + ( 1 + ε ) ( x , y ) ∈ S ∑ ∥ u ( x , y ) − u ( y , x )∥ ≤ A cost g ( C ) , (13) and similarly
cost g ( C ) ≤ A cost g ( f ( C ) ) . (14) \operatorname{cost}_{g}(C)\leq A\operatorname{cost}_{g}(f(C)). \tag*{(14)} cost g ( C ) ≤ A cost g ( f ( C )) . (14) By (11) and (12) ,
cost ( C ) ≤ cost g ( C ) + ε OPT n 8 + ε 4 cost ( C ) + 3 ε 10 ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ . (15) \operatorname{cost}(C)\leq\operatorname{cost}_{g}(C)+\varepsilon\frac{\operatorname{OPT}}{n^{8}}+\frac{\varepsilon}{4}\operatorname{cost}(C)+\frac{3\varepsilon}{10}\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert. \tag*{(15)} cost ( C ) ≤ cost g ( C ) + ε n 8 OPT + 4 ε cost ( C ) + 10 3 ε ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ . (15) cost g ( C ) ≤ cost ( C ) + ε OPT n 8 + ε 4 cost ( C ) + 3 ε 10 ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ . (16) \operatorname{cost}_{g}(C)\leq\operatorname{cost}(C)+\varepsilon\frac{\operatorname{OPT}}{n^{8}}+\frac{\varepsilon}{4}\operatorname{cost}(C)+\frac{3\varepsilon}{10}\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert. \tag*{(16)} cost g ( C ) ≤ cost ( C ) + ε n 8 OPT + 4 ε cost ( C ) + 10 3 ε ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ . (16) cost g ( f ( C ) ) ≤ cost ( f ( C ) ) + 10 ε OPT n 8 + 3 ε cost ( C ) + 3 ε ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ . (17) \operatorname{cost}_{g}(f(C))\leq\operatorname{cost}(f(C))+10\varepsilon\frac{\operatorname{OPT}}{n^{8}}+3\varepsilon\operatorname{cost}(C)+3\varepsilon\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert. \tag*{(17)} cost g ( f ( C )) ≤ cost ( f ( C )) + 10 ε n 8 OPT + 3 ε cost ( C ) + 3 ε ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ . (17) cost ( f ( C ) ) ≤ cost g ( f ( C ) ) + 10 ε OPT n 8 + 3 ε cost ( C ) + 3 ε ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ . (18) \operatorname{cost}(f(C))\leq\operatorname{cost}_{g}(f(C))+10\varepsilon\frac{\operatorname{OPT}}{n^{8}}+3\varepsilon\operatorname{cost}(C)+3\varepsilon\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert. \tag*{(18)} cost ( f ( C )) ≤ cost g ( f ( C )) + 10 ε n 8 OPT + 3 ε cost ( C ) + 3 ε ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ . (18) Here c ∗ ( y ) c^*(y) c ∗ ( y ) y y y OPT / n 8 \operatorname{OPT}/n^8 OPT / n 8 OPT / n 10 \operatorname{OPT}/n^{10} OPT / n 10 n 2 n^2 n 2
It remains to bound ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ \sum_{(x,y)\in S}\lVert y-c^*(y)\rVert ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y )∥ (15) –(18) . By the second conclusion of Theorem 3.3 , Pr [ u ∈ C ∖ C ′ ] ≤ θ \Pr[u\in C\setminus C']\leq\theta Pr [ u ∈ C ∖ C ′ ] ≤ θ u ∈ X u\in X u ∈ X S S S
∀ x , y ∈ X , Pr [ ( x , y ) ∈ S ] ≤ 2 θ . \forall x,y\in X,\qquad\Pr[(x,y)\in S]\leq2\theta. ∀ x , y ∈ X , Pr [( x , y ) ∈ S ] ≤ 2 θ . Orient the pair so that y y y x x x
E [ ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ ] ≤ 2 θ ∑ x , y ∈ X ∣ P x ∗ ∣ ≤ ∣ P y ∗ ∣ ∥ y − c ∗ ( y ) ∥ ≤ 2 θ ∑ y ∈ X k ∣ P y ∗ ∣ ∥ y − c ∗ ( y ) ∥ ≤ 2 θ k ∑ i = 1 k ∑ u , v ∈ P i ∗ ∥ u − v ∥ = 2 θ k OPT , (19) \begin{aligned}
\mathbb{E}\left[\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert\right]
&\leq2\theta\sum_{\substack{x,y\in X\\ |P_x^*|\leq|P_y^*|}}\lVert y-c^*(y)\rVert\\
&\leq2\theta\sum_{y\in X}k|P_y^*|\lVert y-c^*(y)\rVert\\
&\leq2\theta k\sum_{i=1}^{k}\sum_{u,v\in P_i^*}\lVert u-v\rVert=2\theta k\operatorname{OPT}, \tag*{(19)}
\end{aligned} E ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ ≤ 2 θ x , y ∈ X ∣ P x ∗ ∣ ≤ ∣ P y ∗ ∣ ∑ ∥ y − c ∗ ( y )∥ ≤ 2 θ y ∈ X ∑ k ∣ P y ∗ ∣ ∥ y − c ∗ ( y )∥ ≤ 2 θ k i = 1 ∑ k u , v ∈ P i ∗ ∑ ∥ u − v ∥ = 2 θ k OPT , (19) where the last inequality is Lemma 3.5 . By Markov’s inequality, with probability at least 9 / 10 9/10 9/10
∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ ≤ 20 θ k OPT . \sum_{(x,y)\in S}\lVert y-c^*(y)\rVert\leq20\theta k\operatorname{OPT}. ( x , y ) ∈ S ∑ ∥ y − c ∗ ( y )∥ ≤ 20 θ k OPT . Together with Λ \Lambda Λ 4 / 5 4/5 4/5 ε \varepsilon ε (5) and (6) . This concludes the proof of Lemma 3.6 .
Lemma 3.7 (From random clusters to all partitions). Suppose that for every random subset C ⊆ X C \subseteq X C ⊆ X f f f 4 / 5 4/5 4/5
cost ( C ) ≤ A ( cost ( f ( C ) ) + Γ ) and cost ( f ( C ) ) ≤ A ( cost ( C ) + Γ ) , \operatorname{cost}(C) \le A\bigl(\operatorname{cost}(f(C))+\Gamma\bigr) \qquad\text{and} \qquad\operatorname{cost}(f(C)) \le A\bigl(\operatorname{cost}(C)+\Gamma\bigr), cost ( C ) ≤ A ( cost ( f ( C )) + Γ ) and cost ( f ( C )) ≤ A ( cost ( C ) + Γ ) , where A ≤ ( 1 + ε ) 2 A \le(1+\varepsilon)^2 A ≤ ( 1 + ε ) 2 A Γ ≤ ε 2 k OPT A\Gamma\le\frac{\varepsilon}{2k}\operatorname{OPT} A Γ ≤ 2 k ε OPT 4 / 5 4/5 4/5 P \mathcal{P} P X X X
( 1 − ε ) cost ( P ) ≤ ( 1 + ε ) 2 cost ( f ( P ) ) , (1-\varepsilon)\operatorname{cost}(\mathcal{P}) \le(1+\varepsilon)^2\operatorname{cost}(f(\mathcal{P})), ( 1 − ε ) cost ( P ) ≤ ( 1 + ε ) 2 cost ( f ( P )) , cost ( f ( P ) ) ≤ ( 1 + ε ) 3 cost ( P ) . \operatorname{cost}(f(\mathcal{P})) \le(1+\varepsilon)^3\operatorname{cost}(\mathcal{P}). cost ( f ( P )) ≤ ( 1 + ε ) 3 cost ( P ) . Proof. Denote the event in the statement by D D D C ⊆ X C \subseteq X C ⊆ X D D D C = ∅ C=\varnothing C = ∅ P = { P 1 , … , P k } \mathcal{P}=\{P_1,\ldots,P_k\} P = { P 1 , … , P k }
cost ( P ) > ( 1 + ε ) 2 cost ( f ( P ) ) + ε cost ( P ) ≥ A cost ( f ( P ) ) + ε cost ( P ) , \operatorname{cost}(\mathcal{P})>(1+\varepsilon)^2\operatorname{cost}(f(\mathcal{P}))+\varepsilon\operatorname{cost}(\mathcal{P}) \ge A\operatorname{cost}(f(\mathcal{P}))+\varepsilon\operatorname{cost}(\mathcal{P}), cost ( P ) > ( 1 + ε ) 2 cost ( f ( P )) + ε cost ( P ) ≥ A cost ( f ( P )) + ε cost ( P ) , cost ( f ( P ) ) > ( 1 + ε ) 3 cost ( P ) = ( 1 + ε ) 2 cost ( P ) + ε ( 1 + ε ) 2 cost ( P ) ≥ A cost ( P ) + ε cost ( P ) . \operatorname{cost}(f(\mathcal{P}))>(1+\varepsilon)^3\operatorname{cost}(\mathcal{P})=(1+\varepsilon)^2\operatorname{cost}(\mathcal{P})+\varepsilon(1+\varepsilon)^2\operatorname{cost}(\mathcal{P}) \ge A\operatorname{cost}(\mathcal{P})+\varepsilon\operatorname{cost}(\mathcal{P}). cost ( f ( P )) > ( 1 + ε ) 3 cost ( P ) = ( 1 + ε ) 2 cost ( P ) + ε ( 1 + ε ) 2 cost ( P ) ≥ A cost ( P ) + ε cost ( P ) . Thus there is some i ∈ [ k ] i\in[k] i ∈ [ k ]
cost ( P i ) > A cost ( f ( P i ) ) + ε k cost ( P ) , (20) \operatorname{cost}(P_i)>A\operatorname{cost}(f(P_i))+\frac{\varepsilon}{k}\operatorname{cost}(\mathcal{P}), \tag*{(20)} cost ( P i ) > A cost ( f ( P i )) + k ε cost ( P ) , (20) cost ( f ( P i ) ) > A cost ( P i ) + ε k cost ( P ) . (21) \operatorname{cost}(f(P_i))>A\operatorname{cost}(P_i)+\frac{\varepsilon}{k}\operatorname{cost}(\mathcal{P}). \tag*{(21)} cost ( f ( P i )) > A cost ( P i ) + k ε cost ( P ) . (21) Set C = P i C=P_i C = P i i i i
If the random-subset preservation inequalities hold for this choice of C C C
cost ( P i ) ≤ A cost ( f ( P i ) ) + A Γ ≤ A cost ( f ( P i ) ) + ε 2 k cost ( P ) , \operatorname{cost}(P_i)\le A\operatorname{cost}(f(P_i))+A\Gamma\le A\operatorname{cost}(f(P_i))+\frac{\varepsilon}{2k}\operatorname{cost}(\mathcal{P}), cost ( P i ) ≤ A cost ( f ( P i )) + A Γ ≤ A cost ( f ( P i )) + 2 k ε cost ( P ) , and
cost ( f ( P i ) ) ≤ A cost ( P i ) + A Γ ≤ A cost ( P i ) + ε 2 k cost ( P ) , \operatorname{cost}(f(P_i))\le A\operatorname{cost}(P_i)+A\Gamma\le A\operatorname{cost}(P_i)+\frac{\varepsilon}{2k}\operatorname{cost}(\mathcal{P}), cost ( f ( P i )) ≤ A cost ( P i ) + A Γ ≤ A cost ( P i ) + 2 k ε cost ( P ) , because cost ( P ) ≥ OPT \operatorname{cost}(\mathcal{P})\ge\operatorname{OPT} cost ( P ) ≥ OPT (20) and (21) . Therefore, if event D D D C C C 1 / 5 1/5 1/5 D D D 4 / 5 4/5 4/5
Proof of Theorem 1.2. Let ε ′ = ( 1 + ε ) 1 / 3 − 1 = O ( ε ) \varepsilon'=(1+\varepsilon)^{1/3}-1=O(\varepsilon) ε ′ = ( 1 + ε ) 1/3 − 1 = O ( ε )
θ = min { ( ε ′ ) 2 20 , 1 2 ( 1 + ε ′ ) 2 k 2 } . \theta=\min\left\{\frac{(\varepsilon')^2}{20},\frac{1}{2(1+\varepsilon')^2k^2}\right\}. θ = min { 20 ( ε ′ ) 2 , 2 ( 1 + ε ′ ) 2 k 2 1 } . Let
δ ≤ min { θ 7 600 , ( ε ′ ) α d d i m 100 k 2 log 2 n } . \delta\le\min\left\{\frac{\theta^7}{600},\frac{(\varepsilon')^\alpha d_{\mathrm{dim}}}{100k^2\log^2 n}\right\}. δ ≤ min { 600 θ 7 , 100 k 2 log 2 n ( ε ′ ) α d dim } . By Lemma 2.5 , for a sufficiently large constant c > 0 c>0 c > 0
∀ x , y ∈ X , Pr [ ∥ f ( x ) − f ( y ) ∥ ∉ ( 1 ± ε ′ ) ∥ x − y ∥ ] ≤ δ . \forall x,y\in X,\qquad\Pr\left[\lVert f(x)-f(y)\rVert\notin(1\pm\varepsilon')\lVert x-y\rVert\right]\le\delta. ∀ x , y ∈ X , Pr [ ∥ f ( x ) − f ( y )∥ ∈ / ( 1 ± ε ′ ) ∥ x − y ∥ ] ≤ δ . By Lemma 2.8 , the same map has the μ \mu μ
μ ≥ β ( ddim log ( 1 / ε ′ ) + log k + log log n ) . \mu\ge\beta\left(\operatorname{ddim}\log(1/\varepsilon')+\log k+\log\log n\right). μ ≥ β ( ddim log ( 1/ ε ′ ) + log k + log log n ) . We can thus apply Lemma 3.6 . Given our choice of θ \theta θ Γ = ε ′ OPT / ( 2 k ( 1 + ε ′ ) 2 ) \Gamma=\varepsilon'\operatorname{OPT}/(2k(1+\varepsilon')^2) Γ = ε ′ OPT / ( 2 k ( 1 + ε ′ ) 2 ) A ≤ ( 1 + ε ′ ) 2 A\le(1+\varepsilon')^2 A ≤ ( 1 + ε ′ ) 2 A Γ ≤ ε ′ OPT / ( 2 k ) A\Gamma\le\varepsilon'\operatorname{OPT}/(2k) A Γ ≤ ε ′ OPT / ( 2 k ) ε ′ \varepsilon' ε ′
Upper Bound for Aspect Ratio
The proof has three steps. First, in Lemma 3.8 , we assume the existence of a λ \lambda λ n / ( 2 k ) n/(2k) n / ( 2 k ) Lemma 3.9 , we use the bounded aspect ratio to supply such a partition with λ = 4 k 2 Δ \lambda=4k^2\Delta λ = 4 k 2 Δ k k k θ \theta θ Lemma 3.8 satisfies the condition of Lemma 3.7, yielding the logarithmic dependence on Δ \Delta Δ
Lemma 3.8 (Preservation of a Random Cluster). Let X ⊆ R d X\subseteq\mathbb{R}^d X ⊆ R d k k k f : R d → R t f:\mathbb{R}^d\to\mathbb{R}^t f : R d → R t ( ε , δ , ρ ) (\varepsilon,\delta,\rho) ( ε , δ , ρ ) X X X 0 < ε ≤ 1 / 2 0<\varepsilon\le1/2 0 < ε ≤ 1/2
θ ≤ 1 20 , δ ≤ min { θ 7 600 , 1 10 k 3 } , ρ ≤ θ . \theta\le\frac{1}{20},\qquad\delta\le\min\left\{\frac{\theta^7}{600},\frac{1}{10k^3}\right\},\qquad\rho\le\theta. θ ≤ 20 1 , δ ≤ min { 600 θ 7 , 10 k 3 1 } , ρ ≤ θ . Assume that there is a λ \lambda λ P ∗ = { P 1 ∗ , … , P k ∗ } P^*=\{P_1^*,\ldots,P_k^*\} P ∗ = { P 1 ∗ , … , P k ∗ } min i ∈ [ k ] ∣ P i ∗ ∣ ≥ n / ( 2 k ) \min_{i\in[k]}|P_i^*|\ge n/(2k) min i ∈ [ k ] ∣ P i ∗ ∣ ≥ n / ( 2 k ) C ⊆ X C\subseteq X C ⊆ X f f f 4 / 5 4/5 4/5
cost ( C ) ≤ A ( cost ( f ( C ) ) + 400 ( 1 + ε ) λ θ k OPT ) (22) \operatorname{cost}(C)\le A\left(\operatorname{cost}(f(C))+400(1+\varepsilon)\lambda\theta k\operatorname{OPT}\right) \tag*{(22)} cost ( C ) ≤ A ( cost ( f ( C )) + 400 ( 1 + ε ) λ θ k OPT ) (22) cost ( f ( C ) ) ≤ A ( cost ( C ) + 400 ( 1 + ε ) λ θ k OPT ) (23) \operatorname{cost}(f(C))\le A\left(\operatorname{cost}(C)+400(1+\varepsilon)\lambda\theta k\operatorname{OPT}\right) \tag*{(23)} cost ( f ( C )) ≤ A ( cost ( C ) + 400 ( 1 + ε ) λ θ k OPT ) (23) where A = ( 1 + 5 θ ) ( 1 + 2 ε ) A=(1+5\theta)(1+2\varepsilon) A = ( 1 + 5 θ ) ( 1 + 2 ε )
Proof. Let OPT \operatorname{OPT} OPT P ∗ P^* P ∗ λ \lambda λ cost ( P ∗ ) ≤ λ ⋅ OPT \operatorname{cost}(P^*)\le\lambda\cdot\operatorname{OPT} cost ( P ∗ ) ≤ λ ⋅ OPT Λ \Lambda Λ i , j ∈ [ k ] i,j\in[k] i , j ∈ [ k ]
( 1 − ε ) ∑ x ∈ P i ∗ , y ∈ P j ∗ ∥ x − y ∥ ≤ ∑ x ∈ P i ∗ , y ∈ P j ∗ ∥ f ( x ) − f ( y ) ∥ ≤ ( 1 + ε ) ∑ x ∈ P i ∗ , y ∈ P j ∗ ∥ x − y ∥ . (1-\varepsilon)\sum_{x\in P_i^*,y\in P_j^*}\lVert x-y\rVert
\le
\sum_{x\in P_i^*,y\in P_j^*}\lVert f(x)-f(y)\rVert
\le
(1+\varepsilon)\sum_{x\in P_i^*,y\in P_j^*}\lVert x-y\rVert. ( 1 − ε ) x ∈ P i ∗ , y ∈ P j ∗ ∑ ∥ x − y ∥ ≤ x ∈ P i ∗ , y ∈ P j ∗ ∑ ∥ f ( x ) − f ( y )∥ ≤ ( 1 + ε ) x ∈ P i ∗ , y ∈ P j ∗ ∑ ∥ x − y ∥ . Since f f f ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Pr ( Λ ) ≥ 1 − k 2 δ ≥ 9 / 10. \Pr(\Lambda)\ge1-k^2\delta\ge9/10. Pr ( Λ ) ≥ 1 − k 2 δ ≥ 9/10. Let C C C X X X G [ C ] G[C] G [ C ] C C C Theorem 3.3 , there exists C ′ ⊆ C C'\subseteq C C ′ ⊆ C G [ C ′ ] G[C'] G [ C ′ ] θ \theta θ
∀ u ∈ X , Pr [ u ∈ C ∖ C ′ ] ≤ θ . \forall u\in X,\qquad\Pr[u\in C\setminus C']\le\theta. ∀ u ∈ X , Pr [ u ∈ C ∖ C ′ ] ≤ θ . Let
S = { ( x , y ) ∈ C × C : x ∉ C ′ or y ∉ C ′ } . S=\{(x,y)\in C\times C:x\notin C'\text{ or }y\notin C'\}. S = {( x , y ) ∈ C × C : x ∈ / C ′ or y ∈ / C ′ } . For x ∈ X x \in X x ∈ X P x ∗ P_x^* P x ∗ D ∗ D^* D ∗ x x x
g ( x , y ) = { ∥ x − y ∥ , x , y ∈ C ′ , 1 ∣ P x ∗ ∣ ∣ P y ∗ ∣ ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ x ′ − y ′ ∥ , otherwise . g(x,y)=
\begin{cases}
\lVert x-y\rVert, & x,y\in C',\\
\frac{1}{|P_x^*||P_y^*|}\sum_{x'\in P_x^*,y'\in P_y^*}\lVert x'-y'\rVert, & \text{otherwise}.
\end{cases} g ( x , y ) = { ∥ x − y ∥ , ∣ P x ∗ ∣∣ P y ∗ ∣ 1 ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ x ′ − y ′ ∥ , x , y ∈ C ′ , otherwise . and
g f ( x , y ) = { ∥ f ( x ) − f ( y ) ∥ , x , y ∈ C ′ , 1 ∣ P x ∗ ∣ ∣ P y ∗ ∣ ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ f ( x ′ ) − f ( y ′ ) ∥ , otherwise . g_f(x,y)=
\begin{cases}
\lVert f(x)-f(y)\rVert, & x,y\in C',\\
\frac{1}{|P_x^*||P_y^*|}\sum_{x'\in P_x^*,y'\in P_y^*}\lVert f(x')-f(y')\rVert, & \text{otherwise}.
\end{cases} g f ( x , y ) = { ∥ f ( x ) − f ( y )∥ , ∣ P x ∗ ∣∣ P y ∗ ∣ 1 ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ f ( x ′ ) − f ( y ′ )∥ , x , y ∈ C ′ , otherwise . Let
cost g ( C ) = ∑ x , y ∈ C g ( x , y ) , cost g ( f ( C ) ) = ∑ x , y ∈ C g f ( x , y ) . \operatorname{cost}_g(C)=\sum_{x,y\in C}g(x,y), \qquad\operatorname{cost}_g(f(C))=\sum_{x,y\in C}g_f(x,y). cost g ( C ) = x , y ∈ C ∑ g ( x , y ) , cost g ( f ( C )) = x , y ∈ C ∑ g f ( x , y ) . Using Lemma 3.4 for C ′ C' C ′ Λ \Lambda Λ
cost g ( f ( C ) ) ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) ∑ x , y ∈ C ′ ∥ x − y ∥ + ( 1 + ε ) ∑ ( x , y ) ∈ S 1 ∣ P x ∗ ∣ ∣ P y ∗ ∣ ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ x ′ − y ′ ∥ ≤ A cost g ( C ) , (24) \begin{aligned}
\operatorname{cost}_g(f(C)) &\le(1+5\theta)(1+2\varepsilon)\sum_{x,y\in C'}\lVert x-y\rVert\\
&\quad+(1+\varepsilon)\sum_{(x,y)\in S}\frac{1}{|P_x^*||P_y^*|}\sum_{x'\in P_x^*,y'\in P_y^*}\lVert x'-y'\rVert\\
&\le A\operatorname{cost}_g(C), \tag*{(24)}
\end{aligned} cost g ( f ( C )) ≤ ( 1 + 5 θ ) ( 1 + 2 ε ) x , y ∈ C ′ ∑ ∥ x − y ∥ + ( 1 + ε ) ( x , y ) ∈ S ∑ ∣ P x ∗ ∣∣ P y ∗ ∣ 1 x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∑ ∥ x ′ − y ′ ∥ ≤ A cost g ( C ) , (24) and similarly
cost g ( C ) ≤ A cost g ( f ( C ) ) . (25) \operatorname{cost}_g(C)\le A\operatorname{cost}_g(f(C)). \tag*{(25)} cost g ( C ) ≤ A cost g ( f ( C )) . (25) The triangle inequality gives
∣ ∥ x − y ∥ − 1 ∣ P x ∗ ∣ ∣ P y ∗ ∣ ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ x ′ − y ′ ∥ ∣ ≤ 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ + 1 ∣ P y ∗ ∣ ∑ y ′ ∈ P y ∗ ∥ y − y ′ ∥ . (26) \left\lvert\lVert x-y\rVert-\frac{1}{|P_x^*||P_y^*|}\sum_{x'\in P_x^*,y'\in P_y^*}\lVert x'-y'\rVert\right\rvert
\le\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert+\frac{1}{|P_y^*|}\sum_{y'\in P_y^*}\lVert y-y'\rVert. \tag*{(26)} ∥ x − y ∥ − ∣ P x ∗ ∣∣ P y ∗ ∣ 1 x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∑ ∥ x ′ − y ′ ∥ ≤ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ + ∣ P y ∗ ∣ 1 y ′ ∈ P y ∗ ∑ ∥ y − y ′ ∥ . (26) The same inequality, with f ( x ) f(x) f ( x ) f ( y ) f(y) f ( y ) x x x y y y ∣ ∥ f ( x ) − f ( y ) ∥ − g f ( x , y ) ∣ \left\lvert\lVert f(x)-f(y)\rVert-g_f(x,y)\right\rvert ∣ ∥ f ( x ) − f ( y )∥ − g f ( x , y ) ∣
cost ( C ) ≤ A ( cost ( f ( C ) ) + D ) , cost ( f ( C ) ) ≤ A ( cost ( C ) + D ) , \operatorname{cost}(C)\le A\bigl(\operatorname{cost}(f(C))+\mathcal{D}\bigr), \qquad\operatorname{cost}(f(C))\le A\bigl(\operatorname{cost}(C)+\mathcal{D}\bigr), cost ( C ) ≤ A ( cost ( f ( C )) + D ) , cost ( f ( C )) ≤ A ( cost ( C ) + D ) , where
D = ∑ ( x , y ) ∈ S ( 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ + 1 ∣ P y ∗ ∣ ∑ y ′ ∈ P y ∗ ∥ y − y ′ ∥ + 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ f ( x ) − f ( x ′ ) ∥ + 1 ∣ P y ∗ ∣ ∑ y ′ ∈ P y ∗ ∥ f ( y ) − f ( y ′ ) ∥ ) . \mathcal{D}=\sum_{(x,y)\in S}\left(\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert+\frac{1}{|P_y^*|}\sum_{y'\in P_y^*}\lVert y-y'\rVert+\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert f(x)-f(x')\rVert+\frac{1}{|P_y^*|}\sum_{y'\in P_y^*}\lVert f(y)-f(y')\rVert\right). D = ( x , y ) ∈ S ∑ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ + ∣ P y ∗ ∣ 1 y ′ ∈ P y ∗ ∑ ∥ y − y ′ ∥ + ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ f ( x ) − f ( x ′ )∥ + ∣ P y ∗ ∣ 1 y ′ ∈ P y ∗ ∑ ∥ f ( y ) − f ( y ′ )∥ . It remains to show that D \mathcal{D} D
∀ x , y ∈ X , Pr [ ( x , y ) ∈ S ] ≤ 2 θ . \forall x,y\in X,\qquad\Pr\bigl[(x,y)\in S\bigr]\le2\theta. ∀ x , y ∈ X , Pr [ ( x , y ) ∈ S ] ≤ 2 θ . Hence
E [ ∑ ( x , y ) ∈ S 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ ] ≤ 2 θ ∑ x , y ∈ X 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ = 2 θ ∑ x ∈ X n ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ ≤ 4 θ k ∑ x ∈ X ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ ≤ 8 θ k λ ⋅ O P T . (27) \begin{aligned}
\mathbb{E}\left[\sum_{(x,y)\in S}\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert\right]
&\le2\theta\sum_{x,y\in X}\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert\\
&=2\theta\sum_{x\in X}\frac{n}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert\\
&\le4\theta k\sum_{x\in X}\sum_{x'\in P_x^*}\lVert x-x'\rVert\\
&\le8\theta k\lambda\cdot\mathrm{OPT}. \tag*{(27)}
\end{aligned} E ( x , y ) ∈ S ∑ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ ≤ 2 θ x , y ∈ X ∑ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ = 2 θ x ∈ X ∑ ∣ P x ∗ ∣ n x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ ≤ 4 θ k x ∈ X ∑ x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ ≤ 8 θ k λ ⋅ OPT . (27) In addition, for every x , y ∈ X x,y\in X x , y ∈ X
E [ 1 ( x , y ) ∈ S 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ f ( x ) − f ( x ′ ) ∥ ] ≤ 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ E [ ( 1 + ε ) 1 ( x , y ) ∈ S ∥ x − x ′ ∥ ] + 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ E [ max { ∥ f ( x ) − f ( x ′ ) ∥ − ( 1 + ε ) ∥ x − x ′ ∥ , 0 } ] ≤ 3 ( 1 + ε ) θ 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ . (28) \begin{aligned}
\mathbb{E}\left[\mathbf{1}_{(x,y)\in S}\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert f(x)-f(x')\rVert\right]
&\le\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\mathbb{E}\left[(1+\varepsilon)\mathbf{1}_{(x,y)\in S}\lVert x-x'\rVert\right]\\
&\quad+\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\mathbb{E}\left[\max\{\lVert f(x)-f(x')\rVert-(1+\varepsilon)\lVert x-x'\rVert,0\}\right]\\
&\le3(1+\varepsilon)\theta\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert x-x'\rVert. \tag*{(28)}
\end{aligned} E 1 ( x , y ) ∈ S ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ f ( x ) − f ( x ′ )∥ ≤ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ E [ ( 1 + ε ) 1 ( x , y ) ∈ S ∥ x − x ′ ∥ ] + ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ E [ max {∥ f ( x ) − f ( x ′ )∥ − ( 1 + ε ) ∥ x − x ′ ∥ , 0 } ] ≤ 3 ( 1 + ε ) θ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ . (28) Summing this over all x , y x,y x , y ∣ P x ∗ ∣ ≥ n / ( 2 k ) |P_x^*|\ge n/(2k) ∣ P x ∗ ∣ ≥ n / ( 2 k )
E [ ∑ ( x , y ) ∈ S 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ f ( x ) − f ( x ′ ) ∥ ] ≤ 12 ( 1 + ε ) θ k λ ⋅ O P T . \mathbb{E}\left[\sum_{(x,y)\in S}\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\lVert f(x)-f(x')\rVert\right]\le12(1+\varepsilon)\theta k\lambda\cdot\mathrm{OPT}. E ( x , y ) ∈ S ∑ ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ f ( x ) − f ( x ′ )∥ ≤ 12 ( 1 + ε ) θ k λ ⋅ OPT . The same bounds hold for the symmetric y y y
E [ D ] ≤ 40 ( 1 + ε ) θ k λ ⋅ O P T . \mathbb{E}[D]\le40(1+\varepsilon)\theta k\lambda\cdot\mathrm{OPT}. E [ D ] ≤ 40 ( 1 + ε ) θ k λ ⋅ OPT . By Markov’s inequality, Pr [ D ≤ 400 ( 1 + ε ) θ k λ ⋅ O P T ] ≥ 9 / 10 \Pr[D\le400(1+\varepsilon)\theta k\lambda\cdot\mathrm{OPT}]\ge9/10 Pr [ D ≤ 400 ( 1 + ε ) θ k λ ⋅ OPT ] ≥ 9/10 4 / 5 4/5 4/5 Λ \Lambda Λ D D D
Lemma 3.9 (Balanced Partition with Near-Optimal Cost). Let X X X k k k Δ \Delta Δ P = { P 1 , … , P k } \mathcal{P}=\{P_1,\ldots,P_k\} P = { P 1 , … , P k } min i ∈ [ k ] ∣ P i ∣ ≥ n 2 k \min_{i\in[k]}|P_i|\ge\frac{n}{2k} min i ∈ [ k ] ∣ P i ∣ ≥ 2 k n
Then
cost ( P ) ≤ 4 k 2 Δ O P T . \operatorname{cost}(\mathcal{P})\le4k^2\Delta\ \mathrm{OPT}. cost ( P ) ≤ 4 k 2 Δ OPT . Proof. Normalize the minimum positive distance in X X X Δ \Delta Δ P o p t \mathcal{P}^{\mathrm{opt}} P opt P o p t \mathcal{P}^{\mathrm{opt}} P opt n / k n/k n / k
n k ( n k − 1 ) ≥ n 2 4 k 2 \frac{n}{k}\left(\frac{n}{k}-1\right)\ge\frac{n^2}{4k^2} k n ( k n − 1 ) ≥ 4 k 2 n 2 positive-distance pairs, assuming n ≥ 2 k n\ge2k n ≥ 2 k
O P T ≥ n 2 4 k 2 . \mathrm{OPT}\ge\frac{n^2}{4k^2}. OPT ≥ 4 k 2 n 2 . At the same time, every partition has at most n 2 n^2 n 2 Δ \Delta Δ cost ( P ) ≤ n 2 Δ ≤ 4 k 2 Δ OPT \operatorname{cost}(\mathcal{P}) \le n^2\Delta\le4k^2\Delta\operatorname{OPT} cost ( P ) ≤ n 2 Δ ≤ 4 k 2 Δ OPT
Proof of Theorem 1.3. Let ε ′ = ( 1 + ε ) 1 / 3 − 1 = O ( ε ) \varepsilon'=(1+\varepsilon)^{1/3}-1=O(\varepsilon) ε ′ = ( 1 + ε ) 1/3 − 1 = O ( ε ) λ = 4 k 2 Δ \lambda=4k^2\Delta λ = 4 k 2 Δ
θ = min { ( ε ′ ) 2 20 , ε ′ 800 ( 1 + ε ′ ) 3 λ k 2 } . \theta=\min\left\{\frac{(\varepsilon')^2}{20},\frac{\varepsilon'}{800(1+\varepsilon')^3\lambda k^2}\right\}. θ = min { 20 ( ε ′ ) 2 , 800 ( 1 + ε ′ ) 3 λ k 2 ε ′ } . and let
δ ≤ min { θ 7 600 , 1 10 k 3 } , ρ ≤ θ . \delta\le\min\left\{\frac{\theta^7}{600},\frac{1}{10k^3}\right\},\qquad\rho\le\theta. δ ≤ min { 600 θ 7 , 10 k 3 1 } , ρ ≤ θ . By Lemma 2.6 , there is a sufficiently large constant c > 0 c>0 c > 0 f : R d → R t f:\mathbb{R}^d\to\mathbb{R}^t f : R d → R t t ≥ c ε − 2 ( log ( 1 / ε ) + log k + log Δ ) t\ge c\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\log\Delta) t ≥ c ε − 2 ( log ( 1/ ε ) + log k + log Δ ) ( ε ′ , δ ) (\varepsilon',\delta) ( ε ′ , δ ) Lemma 2.7 , f f f ( ε ′ , δ , ρ ) (\varepsilon',\delta,\rho) ( ε ′ , δ , ρ ) P ∗ \mathcal{P}^* P ∗ min i ∣ P i ∗ ∣ ≥ n / ( 2 k ) \min_i|P_i^*|\ge n/(2k) min i ∣ P i ∗ ∣ ≥ n / ( 2 k ) Lemma 3.9 , it achieves λ \lambda λ Lemma 3.8 with ε ′ \varepsilon' ε ′ θ \theta θ Γ = 400 ( 1 + ε ′ ) θ k λ ⋅ OPT \Gamma=400(1+\varepsilon')\theta k\lambda\cdot\operatorname{OPT} Γ = 400 ( 1 + ε ′ ) θ k λ ⋅ OPT A Γ ≤ ε ′ OPT / ( 2 k ) A\Gamma\le\varepsilon'\operatorname{OPT}/(2k) A Γ ≤ ε ′ OPT / ( 2 k )
Generalization to power z z z
We briefly record how the dimension-reduction argument extends from Euclidean distances to their z z z z ≥ 1 z\ge1 z ≥ 1
cost z ( P ) = ∑ i ∑ x , y ∈ P i ∥ x − y ∥ z . \operatorname{cost}_z(\mathcal{P})=\sum_i\sum_{x,y\in P_i}\lVert x-y\rVert^z. cost z ( P ) = i ∑ x , y ∈ P i ∑ ∥ x − y ∥ z . Write OPT z \operatorname{OPT}_z OPT z cost z \operatorname{cost}_z cost z a , b ≥ 0 a,b\ge0 a , b ≥ 0 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1
( a + b ) z ≤ ( 1 + γ ) a z + ( 2 z γ ) z − 1 b z , ( a + b ) z ≤ 2 z − 1 ( a z + b z ) . (29) (a+b)^z\le(1+\gamma)a^z+\left(\frac{2z}{\gamma}\right)^{z-1}b^z,\qquad(a+b)^z\le2^{z-1}(a^z+b^z). \tag*{(29)} ( a + b ) z ≤ ( 1 + γ ) a z + ( γ 2 z ) z − 1 b z , ( a + b ) z ≤ 2 z − 1 ( a z + b z ) . (29) Doubling dimension. We extend Theorem 1.2 to preserve cost z ( P ) \operatorname{cost}_z(\mathcal{P}) cost z ( P ) 1 ± ε 1\pm\varepsilon 1 ± ε k k k P \mathcal{P} P ε ′ = Θ ( ε / z ) \varepsilon'=\Theta(\varepsilon/z) ε ′ = Θ ( ε / z ) Lemma 2.5 with this parameter in the derivation of (7) . Then ( 1 ± ε ′ ) z = 1 ± O ( ε ) (1\pm\varepsilon')^z=1\pm O(\varepsilon) ( 1 ± ε ′ ) z = 1 ± O ( ε ) c j ∗ c_j^* c j ∗ ∑ y ∈ P j ∗ ∥ y − c j ∗ ∥ z \sum_{y\in P_j^*}\lVert y-c_j^*\rVert^z ∑ y ∈ P j ∗ ∥ y − c j ∗ ∥ z OPT \operatorname{OPT} OPT OPT z 1 / z \operatorname{OPT}_z^{1/z} OPT z 1/ z (9) –(10) . Use ( ε ′ r i / 100 ) (\varepsilon'r_i/100) ( ε ′ r i /100 ) Lemma 2.8 to balls of radius ε ′ r i / 100 \varepsilon'r_i/100 ε ′ r i /100 (8) with parameter ε ′ \varepsilon' ε ′ (29) to the inequalities in (11) and (12) gives the corresponding bounds for z z z
∥ x − y ∥ z ≤ ( 1 + γ ) ∥ u ( x , y ) − u ( y , x ) ∥ z + ( 4 z γ ) z − 1 ( ∥ x − u ( x , y ) ∥ z + ∥ y − u ( y , x ) ∥ z ) . \lVert x-y\rVert^z\le(1+\gamma)\lVert u(x,y)-u(y,x)\rVert^z+\left(\frac{4z}{\gamma}\right)^{z-1}\left(\lVert x-u(x,y)\rVert^z+\lVert y-u(y,x)\rVert^z\right). ∥ x − y ∥ z ≤ ( 1 + γ ) ∥ u ( x , y ) − u ( y , x ) ∥ z + ( γ 4 z ) z − 1 ( ∥ x − u ( x , y ) ∥ z + ∥ y − u ( y , x ) ∥ z ) . And also
∥ u ( x , y ) − u ( y , x ) ∥ z ≤ ( 1 + γ ) ∥ x − y ∥ z + ( 4 z γ ) z − 1 ( ∥ x − u ( x , y ) ∥ z + ∥ y − u ( y , x ) ∥ z ) . \lVert u(x,y)-u(y,x)\rVert^z\le(1+\gamma)\lVert x-y\rVert^z+\left(\frac{4z}{\gamma}\right)^{z-1}\left(\lVert x-u(x,y)\rVert^z+\lVert y-u(y,x)\rVert^z\right). ∥ u ( x , y ) − u ( y , x ) ∥ z ≤ ( 1 + γ ) ∥ x − y ∥ z + ( γ 4 z ) z − 1 ( ∥ x − u ( x , y ) ∥ z + ∥ y − u ( y , x ) ∥ z ) . Take γ = ε / 10 \gamma= \varepsilon/10 γ = ε /10 g g g g f g_f g f z z z cost g , z ( C ) \operatorname{cost}_{g,z}(C) cost g , z ( C ) cost g , z ( f ( C ) ) \operatorname{cost}_{g,z}(f(C)) cost g , z ( f ( C ))
Summing the above bounds over all pairs in C C C cost z ( C ) \operatorname{cost}_z(C) cost z ( C ) cost g , z ( C ) \operatorname{cost}_{g,z}(C) cost g , z ( C ) cost g , z ( C ) \operatorname{cost}_{g,z}(C) cost g , z ( C ) cost z ( C ) \operatorname{cost}_z(C) cost z ( C ) cost z ( f ( C ) ) \operatorname{cost}_z(f(C)) cost z ( f ( C )) cost g , z ( f ( C ) ) \operatorname{cost}_{g,z}(f(C)) cost g , z ( f ( C )) ( a + b ) z ≤ 2 z − 1 ( a z + b z ) (a+b)^z \le2^{z-1}(a^z+b^z) ( a + b ) z ≤ 2 z − 1 ( a z + b z ) 2 z − 1 2^{z-1} 2 z − 1 (4) . Consequently, the analogues of (13) –(14) for cost g , z \operatorname{cost}_{g,z} cost g , z ( 1 + ε ) ( 1 + 2 z + 2 θ ) (1+\varepsilon)(1+2^{z+2}\theta) ( 1 + ε ) ( 1 + 2 z + 2 θ ) θ ≤ ε / ( 100 ⋅ 2 z + 2 ) \theta\le\varepsilon/(100\cdot2^{z+2}) θ ≤ ε / ( 100 ⋅ 2 z + 2 ) θ \theta θ Theorem 3.3 is unchanged.
Combining the z z z (13) –(14) and (15) –(18) gives an upper bound on cost z ( C ) \operatorname{cost}_z(C) cost z ( C ) cost z ( f ( C ) ) \operatorname{cost}_z(f(C)) cost z ( f ( C )) cost z ( f ( C ) ) \operatorname{cost}_z(f(C)) cost z ( f ( C )) cost z ( C ) \operatorname{cost}_z(C) cost z ( C ) 1 + O ( ε ) 1+O(\varepsilon) 1 + O ( ε ) O ( ε ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ z + ε OPT z / n 8 ) O\left(\varepsilon\sum_{(x,y)\in S}\lVert y-c^*(y)\rVert^z+\varepsilon\operatorname{OPT}_z/n^8\right) O ( ε ∑ ( x , y ) ∈ S ∥ y − c ∗ ( y ) ∥ z + ε OPT z / n 8 ) z z z (19) then gives (5) and (6) with cost z \operatorname{cost}_z cost z OPT z \operatorname{OPT}_z OPT z 4 / 5 4/5 4/5 cost z \operatorname{cost}_z cost z
Since the pairwise distance estimates use ε ′ = Θ ( ε / z ) \varepsilon'=\Theta(\varepsilon/z) ε ′ = Θ ( ε / z ) z 2 z^2 z 2 ddim log ( z / ε ) \operatorname{ddim}\log(z/\varepsilon) ddim log ( z / ε ) θ \theta θ O ( z ) O(z) O ( z ) log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) δ ≤ θ 7 / 600 \delta\le\theta^7/600 δ ≤ θ 7 /600 t = O ( z 2 ε − 2 ( ddim log ( z / ε ) + log k + log log n + z ) ) t=O\left(z^2\varepsilon^{-2}\left(\operatorname{ddim}\log(z/\varepsilon)+\log k+\log\log n+z\right)\right) t = O ( z 2 ε − 2 ( ddim log ( z / ε ) + log k + log log n + z ) )
We next consider Theorem 1.3, showing that its guarantees also extend to preserving cost z ( P ) \operatorname{cost}_z(\mathcal{P}) cost z ( P ) 1 ± ε 1\pm\varepsilon 1 ± ε P \mathcal{P} P X X X k k k
Aspect ratio. For the proof of Theorem 1.3, we require that, for every fixed A , B ⊆ X A,B\subseteq X A , B ⊆ X 1 − δ 1-\delta 1 − δ
∑ x ∈ A , y ∈ B ∥ f ( x ) − f ( y ) ∥ z ∈ ( 1 ± ε ) ∑ x ∈ A , y ∈ B ∥ x − y ∥ z \sum_{x\in A,y\in B}\lVert f(x)-f(y)\rVert^z \in(1\pm\varepsilon)\sum_{x\in A,y\in B}\lVert x-y\rVert^z x ∈ A , y ∈ B ∑ ∥ f ( x ) − f ( y ) ∥ z ∈ ( 1 ± ε ) x ∈ A , y ∈ B ∑ ∥ x − y ∥ z To this end we apply [36 Theorem 3.5] with one cluster, distortion parameter ε ′ \varepsilon' ε ′ δ \delta δ Z A , B = { ± ( x − y ) : x ∈ A , y ∈ B } Z_{A,B}=\{\pm(x-y):x\in A,y\in B\} Z A , B = { ± ( x − y ) : x ∈ A , y ∈ B } f f f t = O ( z 2 ε − 2 ( log ( 1 / δ ) + z log ( z / ε ) + z 2 ) ) t=O\left(z^2\varepsilon^{-2}\left(\log(1/\delta)+z\log(z/\varepsilon)+z^2\right)\right) t = O ( z 2 ε − 2 ( log ( 1/ δ ) + z log ( z / ε ) + z 2 ) )
We also need that, for every x , y ∈ X x,y\in X x , y ∈ X
E [ max { ∥ f ( x ) − f ( y ) ∥ z − ( 1 + ε ) ∥ x − y ∥ z , 0 } ] ≤ ρ ∥ x − y ∥ z . (30) \mathbb{E}\left[\max\left\{\lVert f(x)-f(y)\rVert^z-(1+\varepsilon)\lVert x-y\rVert^z,0\right\}\right]\le\rho\lVert x-y\rVert^z. \tag*{(30)} E [ max { ∥ f ( x ) − f ( y ) ∥ z − ( 1 + ε ) ∥ x − y ∥ z , 0 } ] ≤ ρ ∥ x − y ∥ z . (30) To this end, we apply [36 Definition 2.1, Lemma C.1, and Claim C.2] with parameter ε ′ \varepsilon' ε ′ ( 1 + ε ′ ) z ≤ 1 + ε (1+\varepsilon')^z\le1+\varepsilon ( 1 + ε ′ ) z ≤ 1 + ε t = O ( z 2 ε − 2 ( z + log ( 1 / ρ ) ) ) t=O\left(z^2\varepsilon^{-2}\left(z+\log(1/\rho)\right)\right) t = O ( z 2 ε − 2 ( z + log ( 1/ ρ ) ) )
Use ε ′ \varepsilon' ε ′ cost z \operatorname{cost}_z cost z λ z = 4 k 2 Δ z \lambda_z=4k^2\Delta^z λ z = 4 k 2 Δ z
The inequalities in (29) give the following z z z (26) :
∥ ∥ x − y ∥ z − 1 ∣ P x ∗ ∣ ∣ P y ∗ ∣ ∑ x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∥ x ′ − y ′ ∥ z ∥ ≤ γ ∥ x − y ∥ z + ( 4 z γ ) z − 1 ( 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ∥ x − x ′ ∥ z + 1 ∣ P y ∗ ∣ ∑ y ′ ∈ P y ∗ ∥ y − y ′ ∥ z ) . (31) \left\lVert\lVert x-y\rVert^z-\frac{1}{\lvert P_x^*\rvert\lvert P_y^*\rvert}\sum_{x'\in P_x^*,y'\in P_y^*}\lVert x'-y'\rVert^z\right\rVert
\le\gamma\lVert x-y\rVert^z+\left(\frac{4z}{\gamma}\right)^{z-1}\left(\frac{1}{\lvert P_x^*\rvert}\sum_{x'\in P_x^*}\lVert x-x'\rVert^z+\frac{1}{\lvert P_y^*\rvert}\sum_{y'\in P_y^*}\lVert y-y'\rVert^z\right). \tag*{(31)} ∥ x − y ∥ z − ∣ P x ∗ ∣ ∣ P y ∗ ∣ 1 x ′ ∈ P x ∗ , y ′ ∈ P y ∗ ∑ ∥ x ′ − y ′ ∥ z ≤ γ ∥ x − y ∥ z + ( γ 4 z ) z − 1 ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ∥ x − x ′ ∥ z + ∣ P y ∗ ∣ 1 y ′ ∈ P y ∗ ∑ ∥ y − y ′ ∥ z . (31) Define
D z = ∑ ( x , y ) ∈ S ( 1 ∣ P x ∗ ∣ ∑ x ′ ∈ P x ∗ ( ∥ x − x ′ ∥ z + ∥ f ( x ) − f ( x ′ ) ∥ z ) + 1 ∣ P y ∗ ∣ ∑ y ′ ∈ P y ∗ ( ∥ y − y ′ ∥ z + ∥ f ( y ) − f ( y ′ ) ∥ z ) ) . \begin{aligned}
D_z = \sum_{(x,y)\in S} \Biggl(&\frac{1}{|P_x^*|}\sum_{x'\in P_x^*}\left(\lVert x-x'\rVert^z+\lVert f(x)-f(x')\rVert^z\right)\\
&+\frac{1}{|P_y^*|}\sum_{y'\in P_y^*}\left(\lVert y-y'\rVert^z+\lVert f(y)-f(y')\rVert^z\right)\Biggr).
\end{aligned} D z = ( x , y ) ∈ S ∑ ( ∣ P x ∗ ∣ 1 x ′ ∈ P x ∗ ∑ ( ∥ x − x ′ ∥ z + ∥ f ( x ) − f ( x ′ ) ∥ z ) + ∣ P y ∗ ∣ 1 y ′ ∈ P y ∗ ∑ ( ∥ y − y ′ ∥ z + ∥ f ( y ) − f ( y ′ ) ∥ z ) ) . Choosing the parameter ρ \rho ρ (30) to satisfy ρ ≤ θ \rho\le\theta ρ ≤ θ z z z (27) and (28) give
E [ D z ] ≤ 40 ( 1 + ε ) θ k λ z ⋅ O P T z . \mathbb{E}[D_z]\le40(1+\varepsilon)\theta k\lambda_z\cdot\mathrm{OPT}_z. E [ D z ] ≤ 40 ( 1 + ε ) θ k λ z ⋅ OPT z . Hence, by Markov’s inequality, D z ≤ 400 ( 1 + ε ) θ k λ z ⋅ O P T z D_z\le400(1+\varepsilon)\theta k\lambda_z\cdot\mathrm{OPT}_z D z ≤ 400 ( 1 + ε ) θ k λ z ⋅ OPT z 9 / 10 9/10 9/10 ( a + b ) z ≤ 2 z − 1 ( a z + b z ) (a+b)^z\le2^{z-1}(a^z+b^z) ( a + b ) z ≤ 2 z − 1 ( a z + b z ) 2 z − 1 2^{z-1} 2 z − 1 (4) . Consequently, the z z z (24) and (25) hold with multiplicative factor ( 1 + 2 z + 2 θ ) / ( 1 − ε ) (1+2^{z+2}\theta)/(1-\varepsilon) ( 1 + 2 z + 2 θ ) / ( 1 − ε ) (31) over S S S f f f (24) and (25) , gives
cost z ( C ) ≤ A ( cost z ( f ( C ) ) + Γ ) , \operatorname{cost}_z(C)\le A\left(\operatorname{cost}_z(f(C))+\Gamma\right), cost z ( C ) ≤ A ( cost z ( f ( C )) + Γ ) , cost z ( f ( C ) ) ≤ A ( cost z ( C ) + Γ ) . \operatorname{cost}_z(f(C))\le A\left(\operatorname{cost}_z(C)+\Gamma\right). cost z ( f ( C )) ≤ A ( cost z ( C ) + Γ ) . where
A = ( 1 + γ ) ( 1 + 2 z + 2 θ ) ( 1 − γ ) ( 1 − ε ) , Γ = 400 ( 1 + ε ) ( 4 z γ ) z − 1 λ z θ k O P T z . A=\frac{(1+\gamma)(1+2^{z+2}\theta)}{(1-\gamma)(1-\varepsilon)},\qquad
\Gamma=400(1+\varepsilon)\left(\frac{4z}{\gamma}\right)^{z-1}\lambda_z\theta k\mathrm{OPT}_z. A = ( 1 − γ ) ( 1 − ε ) ( 1 + γ ) ( 1 + 2 z + 2 θ ) , Γ = 400 ( 1 + ε ) ( γ 4 z ) z − 1 λ z θ k OPT z . For every random C ⊆ X C\subseteq X C ⊆ X f f f 4 / 5 4/5 4/5 D z D_z D z 1 / 10 1/10 1/10 k 2 k^2 k 2 k 2 δ ≤ 1 / 10 k^2\delta\le1/10 k 2 δ ≤ 1/10
θ = min { ε 100 ⋅ 2 z + 2 , ε 800 ( 1 + ε ) 3 λ z k 2 ( γ 4 z ) z − 1 } , δ = min { θ 7 600 , 1 10 k 3 } , ρ = θ . \theta=\min\left\{\frac{\varepsilon}{100\cdot2^{z+2}},\frac{\varepsilon}{800(1+\varepsilon)^3\lambda_z k^2}\left(\frac{\gamma}{4z}\right)^{z-1}\right\},\qquad
\delta=\min\left\{\frac{\theta^7}{600},\frac{1}{10k^3}\right\},\qquad
\rho=\theta. θ = min { 100 ⋅ 2 z + 2 ε , 800 ( 1 + ε ) 3 λ z k 2 ε ( 4 z γ ) z − 1 } , δ = min { 600 θ 7 , 10 k 3 1 } , ρ = θ . With γ = ε / 10 \gamma=\varepsilon/10 γ = ε /10 A ≤ ( 1 + ε ) 2 A\le(1+\varepsilon)^2 A ≤ ( 1 + ε ) 2 A Γ ≤ ε O P T z / ( 2 k ) A\Gamma\le\varepsilon\mathrm{OPT}_z/(2k) A Γ ≤ ε OPT z / ( 2 k ) cost z \operatorname{cost}_z cost z log ( 1 / δ ) = O ( z log ( z / ε ) + log k + z log Δ ) \log(1/\delta)=O(z\log(z/\varepsilon)+\log k+z\log\Delta) log ( 1/ δ ) = O ( z log ( z / ε ) + log k + z log Δ ) t = O ( z 4 ε − 2 ( log ( z / ε ) + log k + z log Δ ) ) t=O(z^4\varepsilon^{-2}(\log(z/\varepsilon)+\log k+z\log\Delta)) t = O ( z 4 ε − 2 ( log ( z / ε ) + log k + z log Δ ))
Lower Bounds
We next prove lower bounds for the two parameters that appear in the dimension reduction theorems above. The first construction rules out a target dimension that is independent of ddim ( X ) \operatorname{ddim}(X) ddim ( X ) ddim ( X ) = O ( 1 ) \operatorname{ddim}(X)=O(1) ddim ( X ) = O ( 1 )
Theorem 3.10 (Lower Bounds for For-All Preservation). There is a universal constant c > 0 c>0 c > 0
For infinitely many n n n X ⊆ R d X\subseteq\mathbb{R}^d X ⊆ R d n n n ddim ( X ) = Θ ( log n ) \operatorname{ddim}(X)=\Theta(\log n) ddim ( X ) = Θ ( log n ) t ≤ c ε − 2 ddim ( X ) t\le c\varepsilon^{-2}\operatorname{ddim}(X) t ≤ c ε − 2 ddim ( X ) X X X
For infinitely many n n n X ⊆ R d X\subseteq\mathbb{R}^d X ⊆ R d n n n t ≤ c ε − 2 log log n t\le c\varepsilon^{-2}\log\log n t ≤ c ε − 2 log log n X X X
Proof. We first give the lower bound showing that a dependence on ddim ( X ) \operatorname{ddim}(X) ddim ( X ) d d d k = 2 k = 2 k = 2
X = { 0 d } n ∪ { e 1 , … , e n } , X = \{0_d\}^{n} \cup\{e_1,\ldots,e_{\sqrt{n}}\}, X = { 0 d } n ∪ { e 1 , … , e n } , where { e i } \{e_i\} { e i } R d \mathbb{R}^d R d X X X Θ ( log n ) \Theta(\log n) Θ ( log n ) n \sqrt{n} n n + 1 \sqrt{n}+1 n + 1
Consider the partition
C 1 ∗ = { 0 d } n , C 2 ∗ = { e 1 , … , e n } . C_1^* = \{0_d\}^{n}, \qquad C_2^* = \{e_1,\ldots,e_{\sqrt{n}}\}. C 1 ∗ = { 0 d } n , C 2 ∗ = { e 1 , … , e n } . The cost satisfies
cost ( C 2 ∗ ) = ∑ i ≠ j ∥ e i − e j ∥ = 2 n ( n − 1 ) ≤ 2 n , \operatorname{cost}(C_2^*) = \sum_{i\ne j}\lVert e_i-e_j\rVert= \sqrt{2}\sqrt{n}(\sqrt{n}-1) \le\sqrt{2}n, cost ( C 2 ∗ ) = i = j ∑ ∥ e i − e j ∥ = 2 n ( n − 1 ) ≤ 2 n , while cost ( C 1 ∗ ) = 0 \operatorname{cost}(C_1^*) = 0 cost ( C 1 ∗ ) = 0 { C 1 , C 2 } \{C_1,C_2\} { C 1 , C 2 } e i e_i e i 0 d 0_d 0 d e i ∈ C 1 e_i \in C_1 e i ∈ C 1 C 1 C_1 C 1 C 1 C_1 C 1 e j ∈ C 1 e_j \in C_1 e j ∈ C 1 j ≠ i j\ne i j = i cost ( C 1 ) ≥ 2 n \operatorname{cost}(C_1) \ge2n cost ( C 1 ) ≥ 2 n C 1 = { 0 d } n ∪ { e i } C_1 = \{0_d\}^{n} \cup\{e_i\} C 1 = { 0 d } n ∪ { e i } C 2 = { e j : j ≠ i } C_2 = \{e_j:j\ne i\} C 2 = { e j : j = i }
cost ( C 1 ) = 2 n , cost ( C 2 ) = 2 ( n − 1 ) ( n − 2 ) > n , \operatorname{cost}(C_1) = 2n, \qquad\operatorname{cost}(C_2) = \sqrt{2}(\sqrt{n}-1)(\sqrt{n}-2) > n, cost ( C 1 ) = 2 n , cost ( C 2 ) = 2 ( n − 1 ) ( n − 2 ) > n , so the total cost exceeds 2 n 2n 2 n
Let π : R d → R t \pi:\mathbb{R}^d \to\mathbb{R}^t π : R d → R t O ( ε − 2 log ( 1 / ε ) ) ≤ t ≤ c ε − 2 ddim ( X ) O(\varepsilon^{-2}\log(1/\varepsilon)) \le t \le c\varepsilon^{-2}\operatorname{ddim}(X) O ( ε − 2 log ( 1/ ε )) ≤ t ≤ c ε − 2 ddim ( X ) c > 0 c>0 c > 0 ddim ( X ) = Θ ( log n ) \operatorname{ddim}(X)=\Theta(\log n) ddim ( X ) = Θ ( log n ) c c c η = 40 ε \eta=40\varepsilon η = 40 ε [29 Lemma 6.3] , for a χ t 2 \chi_t^2 χ t 2 X t X_t X t
Pr [ X t < t 1 + η ] ≥ e − C 0 η 2 t t . \Pr\left[X_t < \frac{t}{1+\eta}\right] \ge\frac{e^{-C_0\eta^2t}}{t}. Pr [ X t < 1 + η t ] ≥ t e − C 0 η 2 t . Choosing the universal constant c c c C 0 η 2 t ≤ 1 100 log n C_0\eta^2t \le\frac{1}{100}\log n C 0 η 2 t ≤ 100 1 log n n n n ε \varepsilon ε 10 n \frac{10}{\sqrt{n}} n 10
1 1 + η ≤ 1 − 10 ε for 0 < ε < 1 / 40 , \sqrt{\frac{1}{1+\eta}} \le1-10\varepsilon\qquad\text{for }0<\varepsilon<1/40, 1 + η 1 ≤ 1 − 10 ε for 0 < ε < 1/40 , we obtain, for each i i i
Pr [ ∥ π e i ∥ ≤ 1 − 10 ε ] ≥ 10 n . \Pr\left[\lVert\pi e_i\rVert\le1-10\varepsilon\right] \ge\frac{10}{\sqrt{n}}. Pr [ ∥ π e i ∥ ≤ 1 − 10 ε ] ≥ n 10 . By independence,
Pr [ ∀ i ∈ [ n ] , ∥ π e i ∥ > 1 − 10 ε ] ≤ 1 10 . \Pr\left[\forall i\in[\sqrt{n}],\ \lVert\pi e_i\rVert> 1-10\varepsilon\right] \le\frac{1}{10}. Pr [ ∀ i ∈ [ n ] , ∥ π e i ∥ > 1 − 10 ε ] ≤ 10 1 . Thus, with probability at least 9 / 10 9/10 9/10 i ∗ i^* i ∗
∥ π e i ∗ ∥ ≤ 1 − 10 ε . (32) \lVert\pi e_{i^*}\rVert\le1-10\varepsilon. \tag*{(32)} ∥ π e i ∗ ∥ ≤ 1 − 10 ε . (32) Additionally, by [Dan21, Lemma 2.1.9], with probability at least 9 / 10 9/10 9/10
∑ i ≠ j ∥ π ( e i ) − π ( e j ) ∥ ∈ ( 1 ± ε ) ∑ i ≠ j ∥ e i − e j ∥ . (33) \sum_{i\ne j}\lVert\pi(e_i)-\pi(e_j)\rVert\in(1\pm\varepsilon)\sum_{i\ne j}\lVert e_i-e_j\rVert. \tag*{(33)} i = j ∑ ∥ π ( e i ) − π ( e j )∥ ∈ ( 1 ± ε ) i = j ∑ ∥ e i − e j ∥ . (33) By a union bound, both events occur with probability at least 8/10. Consider the partition
C 1 = { 0 d } n ∪ { e i ∗ } , C 2 = { e i : i ≠ i ∗ } . C_1 = \{0_d\}^{n} \cup\{e_{i^*}\}, \qquad C_2 = \{e_i : i \ne i^*\}. C 1 = { 0 d } n ∪ { e i ∗ } , C 2 = { e i : i = i ∗ } . Its original cost is
cost ( C 1 , C 2 ) = ( 2 + 2 ) n − 3 2 n + O ( 1 ) . \operatorname{cost}(C_1,C_2) = (2+\sqrt{2})n - 3\sqrt{2}\sqrt{n} + O(1). cost ( C 1 , C 2 ) = ( 2 + 2 ) n − 3 2 n + O ( 1 ) . After projection, using (32) and (33) ,
cost ( π ( C 1 ) , π ( C 2 ) ) ≤ 2 n ( 1 − 10 ε ) + ( 1 + ε ) 2 n ( n − 1 ) ≤ ( 2 + 2 ) n − 15 ε n − 4 2 n < ( 1 − ε ) cost ( C 1 , C 2 ) . \begin{aligned}
\operatorname{cost}(\pi(C_1),\pi(C_2)) &\le2n(1-10\varepsilon) + (1+\varepsilon)\sqrt{2}\sqrt{n}(\sqrt{n}-1) \\
&\le(2+\sqrt{2})n - 15\varepsilon n - 4\sqrt{2}\sqrt{n} \\
&< (1-\varepsilon)\operatorname{cost}(C_1,C_2).
\end{aligned} cost ( π ( C 1 ) , π ( C 2 )) ≤ 2 n ( 1 − 10 ε ) + ( 1 + ε ) 2 n ( n − 1 ) ≤ ( 2 + 2 ) n − 15 ε n − 4 2 n < ( 1 − ε ) cost ( C 1 , C 2 ) . for ε ∈ ( 3 2 / n , 1 / 40 ) \varepsilon\in(3\sqrt{2}/\sqrt{n},1/40) ε ∈ ( 3 2 / n , 1/40 )
For the constant-doubling lower bound, let m ≤ d m \le d m ≤ d
X = { 2 i e i : i ∈ [ m ] } ∪ { 0 d } m 3 2 m . X = \{2^i e_i : i \in[m]\} \cup\{0_d\}^{m^{3^2m}}. X = { 2 i e i : i ∈ [ m ]} ∪ { 0 d } m 3 2 m . This set has constant doubling dimension and satisfies log m = Θ ( log log ∣ X ∣ ) \log m = \Theta(\log\log|X|) log m = Θ ( log log ∣ X ∣ ) η = 40 ε \eta= 40\varepsilon η = 40 ε
O ( ε − 2 log ( 1 / ε ) ) ≤ t ≤ c ε − 2 log m , O(\varepsilon^{-2}\log(1/\varepsilon)) \le t \le c\varepsilon^{-2}\log m, O ( ε − 2 log ( 1/ ε )) ≤ t ≤ c ε − 2 log m , where c > 0 c > 0 c > 0 m m m ε \varepsilon ε 10 / m 10/m 10/ m 9 / 10 9/10 9/10 i ∗ i^* i ∗ ∥ π e i ∗ ∥ ≤ 1 − 10 ε \|\pi e_{i^*}\| \le1-10\varepsilon ∥ π e i ∗ ∥ ≤ 1 − 10 ε 9 / 10 9/10 9/10
∑ i ≠ j ∥ π ( 2 i e i ) − π ( 2 j e j ) ∥ ∈ ( 1 ± ε ) ∑ i ≠ j ∥ 2 i e i − 2 j e j ∥ . \sum_{i\ne j}\|\pi(2^i e_i)-\pi(2^j e_j)\| \in(1\pm\varepsilon)\sum_{i\ne j}\|2^i e_i-2^j e_j\|. i = j ∑ ∥ π ( 2 i e i ) − π ( 2 j e j ) ∥ ∈ ( 1 ± ε ) i = j ∑ ∥ 2 i e i − 2 j e j ∥. Consider the partition
C 1 = { 0 d } m 3 2 m ∪ { 2 i ∗ e i ∗ } , C 2 = { 2 i e i : i ≠ i ∗ } . C_1 = \{0_d\}^{m^{3^2m}} \cup\{2^{i^*}e_{i^*}\}, \qquad C_2 = \{2^i e_i : i \ne i^*\}. C 1 = { 0 d } m 3 2 m ∪ { 2 i ∗ e i ∗ } , C 2 = { 2 i e i : i = i ∗ } . Let
A = m 3 2 m ⋅ 2 i ∗ , T = ∑ i , j ≠ i ∗ ∥ 2 i e i − 2 j e j ∥ . A = m^{3^2m}\cdot2^{i^*}, \qquad T = \sum_{i,j\ne i^*}\|2^i e_i-2^j e_j\|. A = m 3 2 m ⋅ 2 i ∗ , T = i , j = i ∗ ∑ ∥ 2 i e i − 2 j e j ∥. Then cost ( C 1 , C 2 ) = 2 A + T \operatorname{cost}(C_1,C_2) = 2A+T cost ( C 1 , C 2 ) = 2 A + T
S : = ∑ i ≠ j ∥ 2 i e i − 2 j e j ∥ = O ( m 2 m ) . S := \sum_{i\ne j}\|2^i e_i-2^j e_j\| = O(m^{2m}). S := i = j ∑ ∥ 2 i e i − 2 j e j ∥ = O ( m 2 m ) . Since A ≥ 2 m 3 2 m A \ge2m^{3^2m} A ≥ 2 m 3 2 m ε > 1 / m \varepsilon> 1/m ε > 1/ m m m m S ≤ ε A S \le\varepsilon A S ≤ ε A
cost ( π ( C 1 ) , π ( C 2 ) ) ≤ 2 ( 1 − 10 ε ) A + ( 1 + ε ) S ≤ 2 ( 1 − 8 ε ) A < ( 1 − ε ) ( 2 A + T ) = ( 1 − ε ) cost ( C 1 , C 2 ) . \begin{aligned}
\operatorname{cost}(\pi(C_1),\pi(C_2)) &\le2(1-10\varepsilon)A \\
&\quad+ (1+\varepsilon)S \\
&\le2(1-8\varepsilon)A \\
&< (1-\varepsilon)(2A+T) = (1-\varepsilon)\operatorname{cost}(C_1,C_2).
\end{aligned} cost ( π ( C 1 ) , π ( C 2 )) ≤ 2 ( 1 − 10 ε ) A + ( 1 + ε ) S ≤ 2 ( 1 − 8 ε ) A < ( 1 − ε ) ( 2 A + T ) = ( 1 − ε ) cost ( C 1 , C 2 ) . for ε ∈ ( 1 / m , 1 / 40 ) \varepsilon\in(1/m,1/40) ε ∈ ( 1/ m , 1/40 )
One may hope to bypass these lower bounds by preserving only a restricted family of solutions, for instance the O ( 1 ) O(1) O ( 1 ) O ( 1 ) O(1) O ( 1 ) 1 ± ε 1 \pm\varepsilon 1 ± ε
Movement Coresets for Min-Sum k k k
We prove a density-adaptive movement-coreset construction for doubling metrics. The proof first develops a fast annular construction, which is then used as an intermediate reduction before applying the density-adaptive movement scales.
Theorem 1.4 (Density-adaptive coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n ddim ≥ 1 \operatorname{ddim} \ge1 ddim ≥ 1 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 ε \varepsilon ε ( S , w ) (S,w) ( S , w )
∣ S ∣ ≤ ( 1 ε ) O ( ddim ) k log n , |S| \le\left(\frac{1}{\varepsilon}\right)^{O(\operatorname{ddim})} k \log n, ∣ S ∣ ≤ ( ε 1 ) O ( ddim ) k log n , whose movement rule is the nearest-neighbor map. Moreover, such a coreset can be constructed in randomized near-linear time with high probability.
We use the movement-coreset terminology from the introduction. Throughout this section, unless stated otherwise, once a representative set S S S π \pi π S S S w ( s ) = ∣ π − 1 ( s ) ∣ w(s) = |\pi^{-1}(s)| w ( s ) = ∣ π − 1 ( s ) ∣ s ∈ S s \in S s ∈ S
For a weighted set ( S , w ) (S,w) ( S , w ) Q \mathcal{Q} Q S S S
cost S , w ( Q ) = ∑ Q ∈ Q ∑ s , t ∈ Q w ( s ) w ( t ) dist ( s , t ) , \operatorname{cost}_{S,w}(\mathcal{Q}) = \sum_{Q \in\mathcal{Q}} \sum_{s,t \in Q} w(s)w(t)\operatorname{dist}(s,t), cost S , w ( Q ) = Q ∈ Q ∑ s , t ∈ Q ∑ w ( s ) w ( t ) dist ( s , t ) , and, once a movement rule π : X → S \pi: X \to S π : X → S Q \mathcal{Q} Q X X X x ∈ X x \in X x ∈ X Q \mathcal{Q} Q π ( x ) \pi(x) π ( x ) ( Y , w ) (Y,w) ( Y , w )
OPT Y , w = min Q cost Y , w ( Q ) , \operatorname{OPT}_{Y,w} = \min_{\mathcal{Q}} \operatorname{cost}_{Y,w}(\mathcal{Q}), OPT Y , w = Q min cost Y , w ( Q ) , where the minimum is over all partitions of Y Y Y k k k
We will also use the balanced k k k A A A w x w_x w x
W ( A ) = ∑ x ∈ A w x W(A) = \sum_{x \in A} w_x W ( A ) = x ∈ A ∑ w x and define its balanced k k k
cost b k m , w ( A ) = W ( A ) min p ∈ A ∑ x ∈ A w x dist ( x , p ) . \operatorname{cost}_{\mathrm{bkm},w}(A) = W(A) \min_{p \in A} \sum_{x \in A} w_x \operatorname{dist}(x,p). cost bkm , w ( A ) = W ( A ) p ∈ A min x ∈ A ∑ w x dist ( x , p ) . The unweighted case is defined by setting every weight equal to 1. For a partition, cost b k m , w \operatorname{cost}_{\mathrm{bkm},w} cost bkm , w
∑ x , y ∈ A w x w y dist ( x , y ) . \sum_{x,y \in A} w_x w_y \operatorname{dist}(x,y). x , y ∈ A ∑ w x w y dist ( x , y ) . Indeed, by averaging over p ∈ A p \in A p ∈ A w p / W ( A ) w_p/W(A) w p / W ( A )
cost b k m , w ( A ) ≤ ∑ x , y ∈ A w x w y dist ( x , y ) . \operatorname{cost}_{\mathrm{bkm},w}(A) \le\sum_{x,y\in A} w_xw_y \operatorname{dist}(x,y). cost bkm , w ( A ) ≤ x , y ∈ A ∑ w x w y dist ( x , y ) . and by the triangle inequality, for every p ∈ A p \in A p ∈ A
∑ x , y ∈ A w x w y dist ( x , y ) ≤ 2 W ( A ) ∑ x ∈ A w x dist ( x , p ) . \sum_{x,y\in A} w_xw_y \operatorname{dist}(x,y) \le2W(A)\sum_{x\in A}w_x\operatorname{dist}(x,p). x , y ∈ A ∑ w x w y dist ( x , y ) ≤ 2 W ( A ) x ∈ A ∑ w x dist ( x , p ) . Thus, whenever we pass between min-sum and balanced k k k
We will also use the following bicriteria convention throughout the section. Some of the approximation algorithms we invoke may return O ( k ) O(k) O ( k ) k k k k k k O ( k ) O(k) O ( k ) k k k k k k
A Fast Annular Coreset
We begin with an annular coreset construction, which will later be used to reduce the input size before applying the density-adaptive construction.
Lemma 4.1 (Fast annular coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n d d i m \mathrm{ddim} ddim 0 < ε < 1 10 0 < \varepsilon< \frac{1}{10} 0 < ε < 10 1 ε \varepsilon ε ( S , w ) (S,w) ( S , w ) S ⊆ X S \subseteq X S ⊆ X
∣ S ∣ ≤ ( k ε ) O ( d d i m ) log n . |S| \le\left(\frac{k}{\varepsilon}\right)^{O(\mathrm{ddim})}\log n. ∣ S ∣ ≤ ( ε k ) O ( ddim ) log n . The associated movement rule is the nearest-neighbor map. Moreover, the construction can be implemented in randomized near-linear time.
Construction
We start by showing the construction, assuming we have a c c c k k k R = { R 1 , … , R k } \mathcal{R} = \{R_1,\ldots,R_k\} R = { R 1 , … , R k } c i c_i c i R i R_i R i
OPT ^ = ∑ i = 1 k ∣ R i ∣ ∑ x ∈ R i dist ( x , c i ) ≤ c OPT . \widehat{\operatorname{OPT}} = \sum_{i=1}^{k}|R_i|\sum_{x\in R_i}\operatorname{dist}(x,c_i) \le c\operatorname{OPT}. OPT = i = 1 ∑ k ∣ R i ∣ x ∈ R i ∑ dist ( x , c i ) ≤ c OPT . Let
r 0 = 20 OPT ^ , r j = r 0 / 2 j , j = 0 , … , L , r_0 = 20\widehat{\operatorname{OPT}}, \qquad r_j = r_0/2^j,\qquad j=0,\ldots,L, r 0 = 20 OPT , r j = r 0 / 2 j , j = 0 , … , L , where L = ⌈ log 2 ( 40 n 10 ) ⌉ L=\lceil\log_2(40n^{10})\rceil L = ⌈ log 2 ( 40 n 10 )⌉ η \eta η i ∈ [ k ] i\in[k] i ∈ [ k ] j j j η r j \eta r_j η r j
X ∩ B ( c i , r j ) . X\cap B(c_i,r_j). X ∩ B ( c i , r j ) . Let S S S
Lemma 4.2 (Annular movement). For every x ∈ X x\in X x ∈ X
dist ( x , π ( x ) ) ≤ 2 η max { min i ∈ [ k ] dist ( x , c i ) , OPT ^ n 10 } . \operatorname{dist}(x,\pi(x)) \le2\eta\max\left\{\min_{i\in[k]}\operatorname{dist}(x,c_i),\frac{\widehat{\operatorname{OPT}}}{n^{10}}\right\}. dist ( x , π ( x )) ≤ 2 η max { i ∈ [ k ] min dist ( x , c i ) , n 10 OPT } . Proof. Let i i i x ∈ R i x \in R_i x ∈ R i x ∈ R i x \in R_i x ∈ R i ∣ R i ∣ dist ( x , c i ) |R_i|\operatorname{dist}(x,c_i) ∣ R i ∣ dist ( x , c i ) k k k
dist ( x , c i ) ≤ OPT ^ . \operatorname{dist}(x,c_i) \le\widehat{\operatorname{OPT}}. dist ( x , c i ) ≤ OPT . Hence min i dist ( x , c i ) ≤ OPT ^ \min_i \operatorname{dist}(x,c_i) \le\widehat{\operatorname{OPT}} min i dist ( x , c i ) ≤ OPT x x x min i dist ( x , c i ) ≤ OPT ^ / n 10 \min_i \operatorname{dist}(x,c_i) \le\widehat{\operatorname{OPT}}/n^{10} min i dist ( x , c i ) ≤ OPT / n 10 x x x O ( η OPT ^ / n 10 ) O(\eta\widehat{\operatorname{OPT}}/n^{10}) O ( η OPT / n 10 ) j j j
r j + 1 < min i dist ( x , c i ) ≤ r j . r_{j+1} < \min_i \operatorname{dist}(x,c_i) \le r_j. r j + 1 < i min dist ( x , c i ) ≤ r j . The packing at scale r j r_j r j η r j ≤ 2 η min i dist ( x , c i ) \eta r_j \le2\eta\min_i \operatorname{dist}(x,c_i) η r j ≤ 2 η min i dist ( x , c i ) x x x
Lemma 4.3 (Annular preservation). Let X X X d d i m \mathrm{ddim} ddim R R R c c c 0 < ε < 1 / 10 0 < \varepsilon< 1/10 0 < ε < 1/10
η = Θ ( ε c k ) \eta= \Theta\left(\frac{\varepsilon}{ck}\right) η = Θ ( c k ε ) gives an ε \varepsilon ε
Proof. Fix a partition P \mathcal{P} P { x , y } \{x,y\} { x , y } R R R ( x , y ) (x,y) ( x , y ) y ∈ R ℓ y \in R_\ell y ∈ R ℓ y y y x x x
By lemma 4.2, for such a pair,
dist ( x , π ( x ) ) ≤ O ( η ) ( dist ( x , c ℓ ) + OPT ^ n 10 ) ≤ O ( η ) ( dist ( x , y ) + dist ( y , c ℓ ) + OPT ^ n 10 ) , \operatorname{dist}(x,\pi(x)) \le O(\eta)\left(\operatorname{dist}(x,c_\ell) + \frac{\widehat{\operatorname{OPT}}}{n^{10}}\right) \le O(\eta)\left(\operatorname{dist}(x,y) + \operatorname{dist}(y,c_\ell) + \frac{\widehat{\operatorname{OPT}}}{n^{10}}\right), dist ( x , π ( x )) ≤ O ( η ) ( dist ( x , c ℓ ) + n 10 OPT ) ≤ O ( η ) ( dist ( x , y ) + dist ( y , c ℓ ) + n 10 OPT ) , and
dist ( y , π ( y ) ) ≤ O ( η ) ( dist ( y , c ℓ ) + OPT ^ n 10 ) . \operatorname{dist}(y,\pi(y)) \le O(\eta)\left(\operatorname{dist}(y,c_\ell) + \frac{\widehat{\operatorname{OPT}}}{n^{10}}\right). dist ( y , π ( y )) ≤ O ( η ) ( dist ( y , c ℓ ) + n 10 OPT ) . The triangle inequality therefore gives both
dist ( x , y ) ≤ ( 1 + O ( η ) ) dist ( π ( x ) , π ( y ) ) + O ( η ) dist ( y , c ℓ ) + O ( η OPT ^ n 10 ) , (34) \operatorname{dist}(x,y) \le(1+O(\eta))\operatorname{dist}(\pi(x),\pi(y)) + O(\eta)\operatorname{dist}(y,c_\ell) + O\left(\eta\frac{\widehat{\operatorname{OPT}}}{n^{10}}\right), \tag*{(34)} dist ( x , y ) ≤ ( 1 + O ( η )) dist ( π ( x ) , π ( y )) + O ( η ) dist ( y , c ℓ ) + O ( η n 10 OPT ) , (34) dist ( π ( x ) , π ( y ) ) ≤ ( 1 + O ( η ) ) dist ( x , y ) + O ( η ) dist ( y , c ℓ ) + O ( η OPT ^ n 10 ) . (35) \operatorname{dist}(\pi(x),\pi(y)) \le(1+O(\eta))\operatorname{dist}(x,y) + O(\eta)\operatorname{dist}(y,c_\ell) + O\left(\eta\frac{\widehat{\operatorname{OPT}}}{n^{10}}\right). \tag*{(35)} dist ( π ( x ) , π ( y )) ≤ ( 1 + O ( η )) dist ( x , y ) + O ( η ) dist ( y , c ℓ ) + O ( η n 10 OPT ) . (35) It remains to sum the reference-median charge. Fix y ∈ R ℓ y \in R_\ell y ∈ R ℓ y y y ∣ R ℓ ∣ |R_\ell| ∣ R ℓ ∣ k ∣ R ℓ ∣ k|R_\ell| k ∣ R ℓ ∣
∑ dist ( y , c ℓ ) ≤ k ∑ ℓ = 1 k ∣ R ℓ ∣ ∑ y ∈ R ℓ dist ( y , c ℓ ) . \sum\operatorname{dist}(y,c_\ell) \le k\sum_{\ell=1}^{k}|R_\ell|\sum_{y\in R_\ell}\operatorname{dist}(y,c_\ell). ∑ dist ( y , c ℓ ) ≤ k ℓ = 1 ∑ k ∣ R ℓ ∣ y ∈ R ℓ ∑ dist ( y , c ℓ ) . By the definition of the balanced k k k
∑ ℓ = 1 k ∣ R ℓ ∣ ∑ y ∈ R ℓ dist ( y , c ℓ ) = OPT ^ . \sum_{\ell=1}^{k}|R_\ell|\sum_{y\in R_\ell}\operatorname{dist}(y,c_\ell) = \widehat{\operatorname{OPT}}. ℓ = 1 ∑ k ∣ R ℓ ∣ y ∈ R ℓ ∑ dist ( y , c ℓ ) = OPT . Therefore the total charge is at most k O P T ^ k\widehat{\mathrm{OPT}} k OPT O ( η O P T ^ / n 8 ) O(\eta\widehat{\mathrm{OPT}}/n^8) O ( η OPT / n 8 )
Summing (34) and (35) over the oriented pairs and using
O P T ^ ≤ c O P T ≤ c cost ( P ) \widehat{\mathrm{OPT}} \le c\mathrm{OPT} \le c\operatorname{cost}(\mathcal{P}) OPT ≤ c OPT ≤ c cost ( P ) shows that the total error is at most
O ( η c k ) cost ( P ) . O(\eta ck)\operatorname{cost}(\mathcal{P}). O ( η c k ) cost ( P ) . Choosing the hidden constant in η = Θ ( ε / ( c k ) ) \eta= \Theta(\varepsilon/(ck)) η = Θ ( ε / ( c k )) ε \varepsilon ε
Lemma 4.4 (Annular movement-charge bound). Under the assumptions of Lemma 4.3, the annular movement rule π : X → S \pi:X\to S π : X → S can be made to satisfy, for every k k k P \mathcal{P} P of X X X
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) ≤ ε cost ( P ) , \sum_{A\in\mathcal{P}} |A|\sum_{x\in A}\operatorname{dist}(x,\pi(x)) \le\varepsilon\operatorname{cost}(\mathcal{P}), A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) ≤ ε cost ( P ) , by choosing η = C 0 ε / ( c k ) \eta=C_0\varepsilon/(ck) η = C 0 ε / ( c k ) for small enough constant C 0 > 0 C_0>0 C 0 > 0
Proof. For every pair of points in a cluster, label the endpoints so that y ∈ R ℓ y\in R_\ell y ∈ R ℓ
dist ( x , π ( x ) ) + dist ( y , π ( y ) ) ≤ O ( η ) ( dist ( x , y ) + dist ( y , c ℓ ) + O P T ^ n 10 ) . \operatorname{dist}(x,\pi(x))+\operatorname{dist}(y,\pi(y)) \le O(\eta)\left(\operatorname{dist}(x,y)+\operatorname{dist}(y,c_\ell)+\frac{\widehat{\mathrm{OPT}}}{n^{10}}\right). dist ( x , π ( x )) + dist ( y , π ( y )) ≤ O ( η ) ( dist ( x , y ) + dist ( y , c ℓ ) + n 10 OPT ) . Summing over these pairs and using the charging argument from the proof of Lemma 4.3 gives
∑ A ∈ P ( ∣ A ∣ − 1 ) ∑ x ∈ A dist ( x , π ( x ) ) ≤ O ( η ) cost ( P ) + O ( η k O P T ^ ) . \sum_{A\in\mathcal{P}} (|A|-1)\sum_{x\in A}\operatorname{dist}(x,\pi(x)) \le O(\eta)\operatorname{cost}(\mathcal{P})+O(\eta k\widehat{\mathrm{OPT}}). A ∈ P ∑ ( ∣ A ∣ − 1 ) x ∈ A ∑ dist ( x , π ( x )) ≤ O ( η ) cost ( P ) + O ( η k OPT ) . Moreover, Lemma 4.2 and the definition of O P T ^ \widehat{\mathrm{OPT}} OPT
∑ x ∈ X dist ( x , π ( x ) ) ≤ O ( η O P T ^ ) . \sum_{x\in X}\operatorname{dist}(x,\pi(x)) \le O(\eta\widehat{\mathrm{OPT}}). x ∈ X ∑ dist ( x , π ( x )) ≤ O ( η OPT ) . Thus
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) ≤ O ( η ) cost ( P ) + O ( η k O P T ^ ) ≤ O ( η c k ) cost ( P ) , \sum_{A\in\mathcal{P}} |A|\sum_{x\in A}\operatorname{dist}(x,\pi(x)) \le O(\eta)\operatorname{cost}(\mathcal{P})+O(\eta k\widehat{\mathrm{OPT}}) \le O(\eta ck)\operatorname{cost}(\mathcal{P}), A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) ≤ O ( η ) cost ( P ) + O ( η k OPT ) ≤ O ( η c k ) cost ( P ) , Choosing η = C 0 ε / ( c k ) \eta=C_0\varepsilon/(ck) η = C 0 ε / ( c k ) C 0 > 0 C_0>0 C 0 > 0
We next bound the size of the annular coreset by applying Lemma 2.2 to each net.
Lemma 4.5 (Annular size). The annular construction satisfies
∣ S ∣ ≤ ( k / ε ) O ( ddim ) log n . |S|\le(k/\varepsilon)^{O(\operatorname{ddim})}\log n. ∣ S ∣ ≤ ( k / ε ) O ( ddim ) log n . Proof. Lemma 2.2 applied at each center and scale gives
∣ S ∣ ≤ k ( L + 1 ) η − O ( ddim ) = k η − O ( ddim ) log n . |S|\le k(L+1)\eta^{-O(\operatorname{ddim})}=k\eta^{-O(\operatorname{ddim})}\log n. ∣ S ∣ ≤ k ( L + 1 ) η − O ( ddim ) = k η − O ( ddim ) log n . using η \eta η
Obtaining a Constant Approximation Partition
We now explain how to obtain the constant-factor reference partition needed by the final coreset construction. The idea is to start from a poly ( n ) \operatorname{poly}(n) poly ( n ) k k k
Applying this replacement to all clusters proves the constant-factor loss. Thus, if the weighted instance has point set Y Y Y G ′ G' G ′ ∣ Y ∣ |Y| ∣ Y ∣ O ( ∣ Y ∣ log n ) O(|Y|\log n) O ( ∣ Y ∣ log n )
parameter η \eta η OPT ^ ≤ c OPT \widehat{\operatorname{OPT}} \le c\operatorname{OPT} OPT ≤ c OPT k k k P \mathcal{P} P
∣ cost ( P ) − cost ( π ( P ) ) ∣ ≤ O ( η ) cost ( P ) + O ( η k OPT ^ t ) . \left|\operatorname{cost}(\mathcal{P})-\operatorname{cost}(\pi(\mathcal{P}))\right| \le O(\eta)\operatorname{cost}(\mathcal{P})+O(\eta k\widehat{\operatorname{OPT}}_t). ∣ cost ( P ) − cost ( π ( P )) ∣ ≤ O ( η ) cost ( P ) + O ( η k OPT t ) . Both costs in this display are min-sum costs. Choosing η = 1 C ρ k \eta=\frac{1}{C\rho k} η = C ρ k 1 C C C
∣ cost ( P ) − cost ( π ( P ) ) ∣ ≤ 1 100 ρ cost ( P ) + 1 100 ρ OPT ^ t . (36) \left|\operatorname{cost}(\mathcal{P})-\operatorname{cost}(\pi(\mathcal{P}))\right| \le\frac{1}{100\rho}\operatorname{cost}(\mathcal{P})+\frac{1}{100\rho}\widehat{\operatorname{OPT}}_t. \tag*{(36)} ∣ cost ( P ) − cost ( π ( P )) ∣ ≤ 100 ρ 1 cost ( P ) + 100 ρ 1 OPT t . (36) Denote the resulting coreset by ( S t , w t ) (S_t,w_t) ( S t , w t ) Q ~ t \widetilde{Q}_t Q t ρ \rho ρ k k k ( S t , w t ) (S_t,w_t) ( S t , w t ) Claim 5.2 , there is an unsplit partition Q t Q_t Q t
cost S t , w t ( Q t ) ≤ cost ( Q ~ t ) . \operatorname{cost}_{S_t,w_t}(Q_t)\le\operatorname{cost}(\widetilde{Q}_t). cost S t , w t ( Q t ) ≤ cost ( Q t ) . Let P t + 1 P_{t+1} P t + 1 Q t Q_t Q t X X X P ⋆ P^\star P ⋆ X X X
cost ( π ( P t + 1 ) ) ≤ cost ( Q ~ t ) ≤ 2 cost b k m , w ( Q ~ t ) ≤ 2 ρ cost b k m , w ( π ( P ⋆ ) ) ≤ 2 ρ cost ( π ( P ⋆ ) ) . \begin{aligned}
\operatorname{cost}(\pi(P_{t+1})) &\le\operatorname{cost}(\widetilde{Q}_t)\\
&\le2\operatorname{cost}_{\mathrm{bkm},w}(\widetilde{Q}_t)\\
&\le2\rho\operatorname{cost}_{\mathrm{bkm},w}(\pi(P^\star))\\
&\le2\rho\operatorname{cost}(\pi(P^\star)).
\end{aligned} cost ( π ( P t + 1 )) ≤ cost ( Q t ) ≤ 2 cost bkm , w ( Q t ) ≤ 2 ρ cost bkm , w ( π ( P ⋆ )) ≤ 2 ρ cost ( π ( P ⋆ )) . The first and last inequalities are the two directions of the balanced k k k k k k (36) first to P ⋆ P^\star P ⋆ P t + 1 P_{t+1} P t + 1
cost ( P t + 1 ) ≤ O ( ρ ) OPT + 1 4 OPT ^ t . \operatorname{cost}(P_{t+1})\le O(\rho)\operatorname{OPT}+\frac{1}{4}\widehat{\operatorname{OPT}}_t. cost ( P t + 1 ) ≤ O ( ρ ) OPT + 4 1 OPT t . For every part P t + 1 , i P_{t+1,i} P t + 1 , i a t + 1 , i ∈ P t + 1 , i a_{t+1,i}\in P_{t+1,i} a t + 1 , i ∈ P t + 1 , i
∣ P t + 1 , i ∣ ∑ x ∈ P t + 1 , i dist ( x , a t + 1 , i ) ≤ 2 ∑ x , y ∈ P t + 1 , i dist ( x , y ) . |P_{t+1,i}|\sum_{x\in P_{t+1,i}}\operatorname{dist}(x,a_{t+1,i})\le2\sum_{x,y\in P_{t+1,i}}\operatorname{dist}(x,y). ∣ P t + 1 , i ∣ x ∈ P t + 1 , i ∑ dist ( x , a t + 1 , i ) ≤ 2 x , y ∈ P t + 1 , i ∑ dist ( x , y ) . The left-hand side is the contribution of the chosen center to the balanced k k k O ( log n ) O(\log n) O ( log n ) k k k OPT ^ t + 1 \widehat{\operatorname{OPT}}_{t+1} OPT t + 1
OPT ^ t + 1 ≤ 2 cost ( P t + 1 ) ≤ O ( ρ ) OPT + 1 2 OPT ^ t , \widehat{\operatorname{OPT}}_{t+1}\le2\operatorname{cost}(P_{t+1})\le O(\rho)\operatorname{OPT}+\frac{1}{2}\widehat{\operatorname{OPT}}_t, OPT t + 1 ≤ 2 cost ( P t + 1 ) ≤ O ( ρ ) OPT + 2 1 OPT t , which proves the claimed recurrence.
Set T = ⌈ log 2 ( n 2 ) ⌉ T=\lceil\log_2(n^2)\rceil T = ⌈ log 2 ( n 2 )⌉ n 2 / 2 T ≤ 1 n^2/2^T\le1 n 2 / 2 T ≤ 1 OPT ^ T ≤ O ( ρ ) OPT \widehat{\operatorname{OPT}}_T\le O(\rho)\operatorname{OPT} OPT T ≤ O ( ρ ) OPT k k k
cost ( P T ) ≤ 2 cost b k m ( P T ) ≤ 2 OPT ^ T ≤ O ( ρ ) OPT , \operatorname{cost}(P_T)\le2\operatorname{cost}_{\mathrm{bkm}}(P_T)\le2\widehat{\operatorname{OPT}}_T\le O(\rho)\operatorname{OPT}, cost ( P T ) ≤ 2 cost bkm ( P T ) ≤ 2 OPT T ≤ O ( ρ ) OPT , so P T P_T P T O ( ρ ) O(\rho) O ( ρ ) k k k η = Θ ( ε / ( ρ k ) ) \eta=\Theta(\varepsilon/(\rho k)) η = Θ ( ε / ( ρ k )) O ( k log n ) O(k\log n) O ( k log n )
Running Time
A polynomial-factor starting solution is obtained in O ( k n ) O(kn) O ( k n ) [20 ] [37 ] . In each improvement round, the annular construction is run with η = Θ ( 1 / ( ρ k ) ) \eta= \Theta(1/(\rho k)) η = Θ ( 1/ ( ρ k ))
∣ S t ∣ ≤ ( ρ k ) O ( d d i m ) log n . |S_t| \leq(\rho k)^{O(\mathrm{ddim})}\log n. ∣ S t ∣ ≤ ( ρ k ) O ( ddim ) log n . The annular construction uses O ( k log n ) O(k\log n) O ( k log n ) [23 ] , each net can be computed in 2 O ( d d i m ) n log n 2^{O(\mathrm{ddim})}n\log n 2 O ( ddim ) n log n 2 O ( d d i m ) k n log 2 n 2^{O(\mathrm{ddim})}kn\log^2 n 2 O ( ddim ) k n log 2 n
Selecting the new reference centers adds O ( n log n ) O(n\log n) O ( n log n ) O ( log n ) O(\log n) O ( log n ) T = O ( log n ) T = O(\log n) T = O ( log n ) O ( n log 2 n ) O(n\log^2 n) O ( n log 2 n )
We next account for the weighted bicriteria call on this coreset. By remark 4.6, the bipartite graph G ′ G' G ′ ∣ S t ∣ |S_t| ∣ S t ∣ O ( ∣ S t ∣ log n ) O(|S_t|\log n) O ( ∣ S t ∣ log n )
∣ E ( G ′ ) ∣ = O ( ∣ S t ∣ 2 log n ) . |E(G')| = O(|S_t|^2\log n). ∣ E ( G ′ ) ∣ = O ( ∣ S t ∣ 2 log n ) . The Bartal–Charikar–Raz construction then applies the uncapacitated facility-location algorithm of Jain and Vazirani, with modified edge costs. This algorithm runs in O ( ∣ E ( G ′ ) ∣ log ∣ E ( G ′ ) ∣ ) O(|E(G')|\log|E(G')|) O ( ∣ E ( G ′ ) ∣ log ∣ E ( G ′ ) ∣ ) [31 ] , so one bicriteria call takes
O ~ ( ∣ S t ∣ 2 log n ) = O ~ ( ( ρ k ) O ( d d i m ) log 3 n ) . \widetilde{O}(|S_t|^2\log n) = \widetilde{O}\left((\rho k)^{O(\mathrm{ddim})}\log^3 n\right). O ( ∣ S t ∣ 2 log n ) = O ( ( ρ k ) O ( ddim ) log 3 n ) . There are T = ⌈ log 2 ( n 2 ) ⌉ = O ( log n ) T = \lceil\log_2(n^2)\rceil= O(\log n) T = ⌈ log 2 ( n 2 )⌉ = O ( log n )
2 O ( d d i m ) k n log 3 n + O ~ ( ( ρ k ) O ( d d i m ) log 4 n ) . 2^{O(\mathrm{ddim})}kn\log^3 n + \widetilde{O}\left((\rho k)^{O(\mathrm{ddim})}\log^4 n\right). 2 O ( ddim ) k n log 3 n + O ( ( ρ k ) O ( ddim ) log 4 n ) . Apart from the displayed dependence on k k k ρ \rho ρ d d i m \mathrm{ddim} ddim n n n
Proof of the Annular Coreset Lemma
Lemma 4.1 (Fast annular coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n d d i m \mathrm{ddim} ddim 0 < ε < 1 10 0 < \varepsilon< \frac{1}{10} 0 < ε < 10 1 ε \varepsilon ε ( S , w ) (S,w) ( S , w ) S ⊆ X S \subseteq X S ⊆ X
∣ S ∣ ≤ ( k ε ) O ( d d i m ) log n . |S| \leq\left(\frac{k}{\varepsilon}\right)^{O(\mathrm{ddim})}\log n. ∣ S ∣ ≤ ( ε k ) O ( ddim ) log n . The associated movement rule is the nearest-neighbor map. Moreover, the construction can be implemented in randomized near-linear time.
Proof. Assume first that we have a c c c
η = ε β ⋅ c ⋅ k . \eta= \frac{\varepsilon}{\beta\cdot c \cdot k}. η = β ⋅ c ⋅ k ε . for a sufficiently large constant β > 0 \beta> 0 β > 0
A Density-Adaptive Coreset
The density-adaptive coreset removes the factor k k k O P T ^ \widehat{\mathrm{OPT}} OPT
O P T ≤ O P T ^ ≤ c O P T \mathrm{OPT} \le\widehat{\mathrm{OPT}} \le c\mathrm{OPT} OPT ≤ OPT ≤ c OPT for a constant c c c O P T \mathrm{OPT} OPT
For x ∈ X x \in X x ∈ X 2 ≤ m ≤ n 2 \le m \le n 2 ≤ m ≤ n Γ m ( x ) \Gamma_m(x) Γ m ( x ) m m m X X X x x x x x x
γ m ( x ) = 1 m ∑ v ∈ Γ m ( x ) dist ( x , v ) . \gamma_m(x) = \frac{1}{m} \sum_{v \in\Gamma_m(x)} \operatorname{dist}(x,v). γ m ( x ) = m 1 v ∈ Γ m ( x ) ∑ dist ( x , v ) . Set
ρ ( x ) = min 2 ≤ m ≤ n max { γ m ( x ) , O P T ^ k m 2 } . \rho(x) = \min_{2 \le m \le n} \max\left\{ \gamma_m(x), \frac{\widehat{\mathrm{OPT}}}{km^2} \right\}. ρ ( x ) = 2 ≤ m ≤ n min max { γ m ( x ) , k m 2 OPT } . The value ρ ( x ) \rho(x) ρ ( x ) x x x γ m ( x ) \gamma_m(x) γ m ( x ) x x x O P T ^ / ( k m 2 ) \widehat{\mathrm{OPT}}/(km^2) OPT / ( k m 2 )
Construction and Preservation
Let
τ = ε 4 ( c + 1 ) , r min = O P T ^ k n 2 . \tau= \frac{\varepsilon}{4(c+1)}, \qquad r_{\min} = \frac{\widehat{\mathrm{OPT}}}{kn^2}. τ = 4 ( c + 1 ) ε , r m i n = k n 2 OPT . Since the second term in ρ ( x ) \rho(x) ρ ( x ) r min r_{\min} r m i n ρ ( x ) ≥ r min \rho(x) \ge r_{\min} ρ ( x ) ≥ r m i n
H = { x ∈ X : ρ ( x ) > O P T ^ } . H = \{x \in X : \rho(x) > \widehat{\mathrm{OPT}}\}. H = { x ∈ X : ρ ( x ) > OPT } . The points of H H H S S S
J = ⌈ log 2 ( k n 2 ) ⌉ , r j = 2 j r min , J = \left\lceil\log_2(kn^2) \right\rceil, \qquad r_j = 2^j r_{\min}, J = ⌈ log 2 ( k n 2 ) ⌉ , r j = 2 j r m i n , and define the scale rings
R j = { x ∈ X ∖ H : r j ≤ ρ ( x ) < 2 r j } , 0 ≤ j ≤ J . R_j = \{x \in X \setminus H : r_j \le\rho(x) < 2r_j\}, \qquad0 \le j \le J. R j = { x ∈ X ∖ H : r j ≤ ρ ( x ) < 2 r j } , 0 ≤ j ≤ J . For every nonempty ring R j R_j R j ( τ r j ) (\tau r_j) ( τ r j ) S j ⊆ R j S_j \subseteq R_j S j ⊆ R j
S = H ∪ ⋃ j = 0 J S j . S = H \cup\bigcup_{j=0}^{J} S_j. S = H ∪ j = 0 ⋃ J S j . By the convention above, π \pi π H H H x ∈ R j x \in R_j x ∈ R j S j S_j S j τ r j \tau r_j τ r j x x x
dist ( x , π ( x ) ) < τ r j ≤ τ ρ ( x ) . \operatorname{dist}(x,\pi(x)) < \tau r_j \le\tau\rho(x). dist ( x , π ( x )) < τ r j ≤ τ ρ ( x ) . We prove preservation in three steps. First, Lemma 4.8 bounds the total distance moved by the points of a cluster, multiplied by its cardinality. Next, Lemma 4.9 uses the triangle inequality to bound the resulting change in the cluster’s min-sum cost. The additive error per cluster is 2 τ O P T ^ / k 2\tau\widehat{\mathrm{OPT}}/k 2 τ OPT / k k k k O P T ^ ≤ c O P T \widehat{\mathrm{OPT}} \le c\mathrm{OPT} OPT ≤ c OPT Lemma 4.10 .
Lemma 4.8 (Movement charge). Let A ⊆ X A \subseteq X A ⊆ X m ≥ 2 m \ge2 m ≥ 2
∀ x ∈ A , dist ( x , π ( x ) ) ≤ τ ρ ( x ) . \forall x \in A,\qquad\operatorname{dist}(x,\pi(x)) \le\tau\rho(x). ∀ x ∈ A , dist ( x , π ( x )) ≤ τ ρ ( x ) . Then
m ∑ x ∈ A dist ( x , π ( x ) ) ≤ τ cost ( A ) + O P T ^ k . m \sum_{x \in A} \operatorname{dist}(x,\pi(x)) \le\tau\operatorname{cost}(A) + \frac{\widehat{\mathrm{OPT}}}{k}. m x ∈ A ∑ dist ( x , π ( x )) ≤ τ cost ( A ) + k OPT . Proof. Fix x ∈ A x \in A x ∈ A m m m x x x A A A
m γ m ( x ) = ∑ v ∈ V m ( x ) dist ( x , v ) ≤ ∑ y ∈ A dist ( x , y ) . m\gamma_m(x) = \sum_{v \in V_m(x)} \operatorname{dist}(x,v) \le\sum_{y \in A} \operatorname{dist}(x,y). m γ m ( x ) = v ∈ V m ( x ) ∑ dist ( x , v ) ≤ y ∈ A ∑ dist ( x , y ) . By definition of ρ ( x ) \rho(x) ρ ( x )
ρ ( x ) ≤ γ m ( x ) + O P T ^ k m 2 . \rho(x) \le\gamma_m(x) + \frac{\widehat{\mathrm{OPT}}}{km^2}. ρ ( x ) ≤ γ m ( x ) + k m 2 OPT . Multiplying by m m m x ∈ A x \in A x ∈ A dist ( x , π ( x ) ) ≤ τ ρ ( x ) \operatorname{dist}(x,\pi(x)) \le\tau\rho(x) dist ( x , π ( x )) ≤ τ ρ ( x )
Lemma 4.9 (One cluster). Let A ⊆ X A \subseteq X A ⊆ X m ≥ 2 m \ge2 m ≥ 2
∣ cost ( A ) − ∑ x , y ∈ A dist ( π ( x ) , π ( y ) ) ∣ ≤ 2 τ cost ( A ) + 2 τ O P T ^ k . \left|\operatorname{cost}(A) - \sum_{x,y \in A} \operatorname{dist}(\pi(x),\pi(y))\right| \le2\tau\operatorname{cost}(A) + \frac{2\tau\widehat{\mathrm{OPT}}}{k}. cost ( A ) − x , y ∈ A ∑ dist ( π ( x ) , π ( y )) ≤ 2 τ cost ( A ) + k 2 τ OPT . Proof. For every x , y ∈ A x,y \in A x , y ∈ A
∣ dist ( x , y ) − dist ( π ( x ) , π ( y ) ) ∣ ≤ dist ( x , π ( x ) ) + dist ( y , π ( y ) ) . \left|\operatorname{dist}(x,y) - \operatorname{dist}(\pi(x),\pi(y))\right| \le\operatorname{dist}(x,\pi(x)) + \operatorname{dist}(y,\pi(y)). ∣ dist ( x , y ) − dist ( π ( x ) , π ( y )) ∣ ≤ dist ( x , π ( x )) + dist ( y , π ( y )) . Summing over all ordered pairs x , y ∈ A x,y \in A x , y ∈ A
∣ cost ( A ) − ∑ x , y ∈ A dist ( π ( x ) , π ( y ) ) ∣ ≤ 2 ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) . \left|\operatorname{cost}(A) - \sum_{x,y \in A} \operatorname{dist}(\pi(x),\pi(y))\right| \le2|A| \sum_{x \in A} \operatorname{dist}(x,\pi(x)). cost ( A ) − x , y ∈ A ∑ dist ( π ( x ) , π ( y )) ≤ 2∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) . The claim now follows from lemma 4.8.
Lemma 4.10 (Density-adaptive preservation). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n dim \operatorname{dim} dim
O P T ≤ O P T ^ ≤ c O P T . \mathrm{OPT} \le\widehat{\mathrm{OPT}} \le c\mathrm{OPT}. OPT ≤ OPT ≤ c OPT . For every 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 ε \varepsilon ε
Proof. Let P \mathcal{P} P k k k
∣ cost ( P ) − ∑ P ∈ P ∑ x , y ∈ P dist ( π ( x ) , π ( y ) ) ∣ ≤ 2 τ cost ( P ) + 2 τ O P T ^ . \left|\operatorname{cost}(\mathcal{P}) - \sum_{P \in\mathcal{P}}\sum_{x,y \in P} \operatorname{dist}(\pi(x),\pi(y))\right| \le2\tau\operatorname{cost}(\mathcal{P}) + 2\tau\widehat{\mathrm{OPT}}. cost ( P ) − P ∈ P ∑ x , y ∈ P ∑ dist ( π ( x ) , π ( y )) ≤ 2 τ cost ( P ) + 2 τ OPT . Since
O P T ^ ≤ c O P T ≤ c cost ( P ) , \widehat{\mathrm{OPT}} \le c\mathrm{OPT} \le c\operatorname{cost}(\mathcal{P}), OPT ≤ c OPT ≤ c cost ( P ) , the right-hand side is at most
2 τ ( c + 1 ) cost ( P ) . 2\tau(c+1)\operatorname{cost}(\mathcal{P}). 2 τ ( c + 1 ) cost ( P ) . With τ = ε / ( 4 ( c + 1 ) ) \tau= \varepsilon/(4(c+1)) τ = ε / ( 4 ( c + 1 )) ε cost ( P ) \varepsilon\operatorname{cost}(\mathcal{P}) ε cost ( P )
The preceding argument gives more than preservation of the total cost: it also bounds the sum of the movement terms used in the triangle-inequality estimate.
Lemma 4.11 (Density-adaptive movement-charge bound). Under the assumptions of Lemma 4.10 , the density-adaptive movement rule π : X → S \pi: X \to S π : X → S satisfies, for every k k k partition P \mathcal{P} P of X X X
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) ≤ ε cost ( P ) . \sum_{A \in\mathcal{P}} |A| \sum_{x \in A} \operatorname{dist}(x,\pi(x)) \le\varepsilon\operatorname{cost}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) ≤ ε cost ( P ) . Proof. Write d x = dist ( x , π ( x ) ) d_x = \operatorname{dist}(x,\pi(x)) d x = dist ( x , π ( x )) d x > 0 d_x > 0 d x > 0 γ 2 ( x ) ≤ d x / 2 \gamma_2(x) \le d_x/2 γ 2 ( x ) ≤ d x /2
d x ≤ τ ρ ( x ) ≤ τ ( d x 2 + O P T ^ 4 k ) . d_x \le\tau\rho(x) \le\tau\left(\frac{d_x}{2} + \frac{\widehat{\mathrm{OPT}}}{4k}\right). d x ≤ τ ρ ( x ) ≤ τ ( 2 d x + 4 k OPT ) . This inequality also holds for d x = 0 d_x = 0 d x = 0 x ∈ X x \in X x ∈ X d x ≤ τ O P T ^ / ( 2 k ) d_x \le\tau\widehat{\mathrm{OPT}}/(2k) d x ≤ τ OPT / ( 2 k ) Lemma 4.8 and summing over P \mathcal{P} P
∑ A ∈ P ∣ A ∣ ∑ x ∈ A d x ≤ τ cost ( P ) + τ O P T ^ ≤ τ ( c + 1 ) cost ( P ) ≤ ε cost ( P ) . \sum_{A \in\mathcal{P}} |A| \sum_{x \in A} d_x \le\tau\operatorname{cost}(\mathcal{P}) + \tau\widehat{\mathrm{OPT}} \le\tau(c+1)\operatorname{cost}(\mathcal{P}) \le\varepsilon\operatorname{cost}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ d x ≤ τ cost ( P ) + τ OPT ≤ τ ( c + 1 ) cost ( P ) ≤ ε cost ( P ) . Size Bound
Lemma 4.12 (High-scale points). The set H H H has size at most k k k
Proof. If x ∈ H x \in H x ∈ H ρ ( x ) \rho(x) ρ ( x )
O P T ^ < ρ ( x ) ≤ max { γ 2 ( x ) , O P T ^ 4 k } . \widehat{\mathrm{OPT}} < \rho(x) \le\max\left\{\gamma_2(x), \frac{\widehat{\mathrm{OPT}}}{4k}\right\}. OPT < ρ ( x ) ≤ max { γ 2 ( x ) , 4 k OPT } . Hence γ 2 ( x ) > O P T ^ \gamma_2(x) > \widehat{\mathrm{OPT}} γ 2 ( x ) > OPT x x x 2 O P T ^ 2\widehat{\mathrm{OPT}} 2 OPT ∣ H ∣ > k |H| > k ∣ H ∣ > k H H H O P T \mathrm{OPT} OPT 2 O P T ^ ≥ 2 O P T 2\widehat{\mathrm{OPT}} \ge2\mathrm{OPT} 2 OPT ≥ 2 OPT
Lemma 4.13 (Single scale ring). For every scale ring R j R_j R j
∣ S j ∣ ≤ 3 k ( C τ ) d d i m |S_j| \le3k\left(\frac{C}{\tau}\right)^{\mathrm{ddim}} ∣ S j ∣ ≤ 3 k ( τ C ) ddim for a universal constant C > 0 C > 0 C > 0
Proof. Fix a ring R j R_j R j r = r j r = r_j r = r j S r = S j S_r = S_j S r = S j N r ⊆ S r N_r \subseteq S_r N r ⊆ S r ( 16 r ) (16r) ( 16 r ) S r S_r S r s ∈ S r s \in S_r s ∈ S r N r N_r N r F v F_v F v v ∈ N r v \in N_r v ∈ N r F v ⊆ B ( v , 16 r ) F_v \subseteq B(v,16r) F v ⊆ B ( v , 16 r ) S r S_r S r ( τ r ) (\tau r) ( τ r ) F v F_v F v τ r \tau r τ r Lemma 2.2 ,
∣ F v ∣ ≤ ( C τ ) d d i m . |F_v| \le\left(\frac{C}{\tau}\right)^{\mathrm{ddim}}. ∣ F v ∣ ≤ ( τ C ) ddim . Thus
∣ S r ∣ ≤ ∣ N r ∣ ( C τ ) d d i m . |S_r| \le|N_r|\left(\frac{C}{\tau}\right)^{\mathrm{ddim}}. ∣ S r ∣ ≤ ∣ N r ∣ ( τ C ) ddim . It remains to prove ∣ N r ∣ < 3 k |N_r| < 3k ∣ N r ∣ < 3 k
Let T = ∣ N r ∣ T = |N_r| T = ∣ N r ∣ v ∈ N r v \in N_r v ∈ N r v ∈ R j v \in R_j v ∈ R j ρ ( v ) < 2 r \rho(v) < 2r ρ ( v ) < 2 r m v m_v m v m m m ρ ( v ) \rho(v) ρ ( v )
γ m v ( v ) < 2 r , O P T ^ k m v 2 < 2 r . \gamma_{m_v}(v) < 2r, \qquad\frac{\widehat{\mathrm{OPT}}}{k m_v^2} < 2r. γ m v ( v ) < 2 r , k m v 2 OPT < 2 r . The second inequality gives
m v > O P T ^ 2 k r , m_v > \sqrt{\frac{\widehat{\mathrm{OPT}}}{2kr}}, m v > 2 k r OPT , and the first implies that more than half of the points in Γ m v ( v ) \Gamma_{m_v}(v) Γ m v ( v ) B ( v , 4 r ) B(v,4r) B ( v , 4 r )
Define
h : = ⌊ O P T ^ 8 k r ⌋ . h := \left\lfloor\sqrt{\frac{\widehat{\mathrm{OPT}}}{8kr}} \right\rfloor. h := 8 k r OPT . Since m v > 2 O P T ^ / ( 8 k r ) m_v > 2\sqrt{\widehat{\mathrm{OPT}}/(8kr)} m v > 2 OPT / ( 8 k r ) B ( v , 4 r ) B(v,4r) B ( v , 4 r ) h h h v ∈ N r v \in N_r v ∈ N r
G v ⊆ B ( v , 4 r ) , ∣ G v ∣ = h . G_v \subseteq B(v,4r), \qquad|G_v| = h. G v ⊆ B ( v , 4 r ) , ∣ G v ∣ = h . The choice of h h h
r h 2 ≥ O P T ^ 32 k ≥ O P T 32 k . rh^2 \ge\frac{\widehat{\mathrm{OPT}}}{32k} \ge\frac{\mathrm{OPT}}{32k}. r h 2 ≥ 32 k OPT ≥ 32 k OPT . Distinct points of N r N_r N r 16 r 16r 16 r x ∈ G v x \in G_v x ∈ G v y ∈ G v ′ y \in G_{v'} y ∈ G v ′ v ≠ v ′ v \ne v' v = v ′
dist ( x , y ) ≥ 16 r − 4 r − 4 r = 8 r . \operatorname{dist}(x,y) \ge16r - 4r - 4r = 8r. dist ( x , y ) ≥ 16 r − 4 r − 4 r = 8 r . The sets G v G_v G v
Let O 1 , … , O k O_1,\ldots,O_k O 1 , … , O k X X X v ∈ N r v \in N_r v ∈ N r a ∈ [ k ] a \in[k] a ∈ [ k ]
g v a = ∣ G v ∩ O a ∣ , M a = ∑ v ∈ N r g v a . g_{va} = |G_v \cap O_a|, \qquad M_a = \sum_{v\in N_r} g_{va}. g v a = ∣ G v ∩ O a ∣ , M a = v ∈ N r ∑ g v a . The number Q Q Q G v G_v G v
Q = ∑ a = 1 k M a 2 − ∑ v ∈ N r ∑ a = 1 k g v a 2 . Q = \sum_{a=1}^{k} M_a^2 - \sum_{v\in N_r}\sum_{a=1}^{k} g_{va}^2. Q = a = 1 ∑ k M a 2 − v ∈ N r ∑ a = 1 ∑ k g v a 2 . Since ∑ a M a = ∑ v ∈ N r ∣ G v ∣ = T h \sum_a M_a = \sum_{v\in N_r}|G_v| = Th ∑ a M a = ∑ v ∈ N r ∣ G v ∣ = T h
∑ a = 1 k M a 2 ≥ ( T h ) 2 k , \sum_{a=1}^{k} M_a^2 \ge\frac{(Th)^2}{k}, a = 1 ∑ k M a 2 ≥ k ( T h ) 2 , and for every v v v
∑ a = 1 k g v a 2 ≤ h 2 . \sum_{a=1}^{k} g_{va}^2 \le h^2. a = 1 ∑ k g v a 2 ≤ h 2 . Thus
Q ≥ h 2 ( T 2 k − T ) . Q \ge h^2\left(\frac{T^2}{k}-T\right). Q ≥ h 2 ( k T 2 − T ) . Every pair counted by Q Q Q 8 r 8r 8 r
O P T ≥ 8 r h 2 ( T 2 k − T ) . \mathrm{OPT} \ge8rh^2\left(\frac{T^2}{k}-T\right). OPT ≥ 8 r h 2 ( k T 2 − T ) . If T ≤ k T \le k T ≤ k r h 2 ≥ O P T / ( 32 k ) rh^2 \ge\mathrm{OPT}/(32k) r h 2 ≥ OPT / ( 32 k )
T 2 k − T ≤ 4 k . \frac{T^2}{k}-T \le4k. k T 2 − T ≤ 4 k . Hence T 2 − k T − 4 k 2 ≤ 0 T^2-kT-4k^2 \le0 T 2 − k T − 4 k 2 ≤ 0
T ≤ 1 + 17 2 k < 3 k . T \le\frac{1+\sqrt{17}}{2}k < 3k. T ≤ 2 1 + 17 k < 3 k . This proves the lemma.
Lemma 4.14 (Total size). The set S S S
∣ S ∣ ≤ k ( c + 1 ε ) O ( d d i m ) log ( 2 n ) . |S| \le k\left(\frac{c+1}{\varepsilon}\right)^{O(\mathrm{ddim})}\log(2n). ∣ S ∣ ≤ k ( ε c + 1 ) O ( ddim ) log ( 2 n ) . Proof. By lemma 4.12, ∣ H ∣ ≤ k |H| \le k ∣ H ∣ ≤ k
3 k ( C τ ) d d i m 3k\left(\frac{C}{\tau}\right)^{\mathrm{ddim}} 3 k ( τ C ) ddim representatives. There are
J + 1 ≤ 2 + log 2 ( k n 2 ) = O ( log n ) J+1 \le2+\log_2(kn^2)=O(\log n) J + 1 ≤ 2 + log 2 ( k n 2 ) = O ( log n ) rings. Substituting τ = ε / ( 4 ( c + 1 ) ) \tau=\varepsilon/(4(c+1)) τ = ε / ( 4 ( c + 1 ))
Weighted Implementation and Composition
We use the density-adaptive construction on weighted instances only when the weights are integer multiplicities. For a weighted support ( Y , w ) (Y,w) ( Y , w ) Y ( w ) Y^{(w)} Y ( w ) w ( y ) w(y) w ( y ) y ∈ Y y\in Y y ∈ Y
N = ∑ y ∈ Y w ( y ) . N=\sum_{y\in Y}w(y). N = y ∈ Y ∑ w ( y ) . The quantities Γ m ( y ) \Gamma_m(y) Γ m ( y ) γ m ( y ) \gamma_m(y) γ m ( y ) ρ ( y ) \rho(y) ρ ( y ) Y ( w ) Y^{(w)} Y ( w ) 2 ≤ m ≤ N 2\le m\le N 2 ≤ m ≤ N Y Y Y
Lemma 4.15 (Weighted density-adaptive construction). Let ( Y , w ) (Y,w) ( Y , w ) N N N d d i m \mathrm{ddim} ddim
O P T Y , w ≤ O P T ^ ≤ c O P T Y , w . \mathrm{OPT}_{Y,w}\le\widehat{\mathrm{OPT}}\le c\mathrm{OPT}_{Y,w}. OPT Y , w ≤ OPT ≤ c OPT Y , w . Then the weighted density-adaptive construction gives an ε \varepsilon ε ( Y , w ) (Y,w) ( Y , w )
k ( c + 1 ε ) O ( ddim ) log ( 2 N ) . k\left(\frac{c+1}{\varepsilon}\right)^{O(\operatorname{ddim})}\log(2N). k ( ε c + 1 ) O ( ddim ) log ( 2 N ) . Moreover, its movement rule satisfies the movement-charge bound of Lemma 4.11 , with Y ( w ) Y^{(w)} Y ( w ) X X X
Proof. Apply the unweighted density-adaptive construction to the multiset Y ( w ) Y^{(w)} Y ( w ) Claim 5.2 , an optimal partition of Y ( w ) Y^{(w)} Y ( w ) OPT Y , w \operatorname{OPT}_{Y,w} OPT Y , w Lemma 4.10 , Lemma 4.11 , and Lemma 4.14 , applied with input size N N N Y ( w ) Y^{(w)} Y ( w )
It remains only to write the result in weighted form. Since coincident copies have distance zero, the nets in the construction may be chosen with at most one representative at each support point. We store these support representatives and give each representative the total multiplicity of the copies mapped to it. With this compressed notation, the moved multiset cost is exactly the weighted cost. Thus the same guarantees hold for the weighted instance ( Y , w ) (Y,w) ( Y , w )
Lemma 4.16 (Computing weighted densities). Let M = ∣ Y ∣ M=|Y| M = ∣ Y ∣ ρ ( y ) \rho(y) ρ ( y ) ( Y , w ) (Y,w) ( Y , w )
O ( M 2 ( log M + log N ) ) . O\left(M^2(\log M+\log N)\right). O ( M 2 ( log M + log N ) ) . Proof. Fix y ∈ Y y\in Y y ∈ Y y 1 , … , y M y_1,\ldots,y_M y 1 , … , y M y y y
P q = ∑ i ≤ q w ( y i ) , D q = ∑ i ≤ q w ( y i ) dist ( y , y i ) . P_q=\sum_{i\le q}w(y_i),\qquad D_q=\sum_{i\le q}w(y_i)\operatorname{dist}(y,y_i). P q = i ≤ q ∑ w ( y i ) , D q = i ≤ q ∑ w ( y i ) dist ( y , y i ) . If P q − 1 < m ≤ P q P_{q-1}<m\le P_q P q − 1 < m ≤ P q m m m y y y y 1 , … , y q − 1 y_1,\ldots,y_{q-1} y 1 , … , y q − 1 m − P q − 1 m-P_{q-1} m − P q − 1 y q y_q y q
γ m ( y ) = D q − 1 + ( m − P q − 1 ) dist ( y , y q ) m . \gamma_m(y)=\frac{D_{q-1}+(m-P_{q-1})\operatorname{dist}(y,y_q)}{m}. γ m ( y ) = m D q − 1 + ( m − P q − 1 ) dist ( y , y q ) . Because the support points are sorted by distance from y y y D q − 1 ≤ P q − 1 dist ( y , y q ) D_{q-1}\le P_{q-1}\operatorname{dist}(y,y_q) D q − 1 ≤ P q − 1 dist ( y , y q ) m m m OPT ^ / ( k m 2 ) \widehat{\operatorname{OPT}}/(km^2) OPT / ( k m 2 ) m m m O ( log N ) O(\log N) O ( log N ) M M M y y y y y y
Corollary 4.17 (Density-adaptive coreset after annular reduction). Let ( Y , w ) (Y,w) ( Y , w ) ( ε / 10 ) (\varepsilon/10) ( ε /10 ) X X X
OPT Y , w ≤ OPT ^ ≤ c OPT Y , w . \operatorname{OPT}_{Y,w}\le\widehat{\operatorname{OPT}}\le c\operatorname{OPT}_{Y,w}. OPT Y , w ≤ OPT ≤ c OPT Y , w . for a universal constant c c c ( Y , w ) (Y,w) ( Y , w ) OPT ^ \widehat{\operatorname{OPT}} OPT ε / 10 \varepsilon/10 ε /10 T T T ν : X → T \nu:X\to T ν : X → T ε \varepsilon ε X X X ν \nu ν
k ( 1 ε ) O ( ddim ) log n . k\left(\frac{1}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n. k ( ε 1 ) O ( ddim ) log n . If M = ∣ Y ∣ M=|Y| M = ∣ Y ∣ ( Y , w ) (Y,w) ( Y , w )
O ( M 2 ( log M + log n ) ) . O\left(M^2(\log M+\log n)\right). O ( M 2 ( log M + log n ) ) . Proof. Let π : X → Y \pi: X \to Y π : X → Y ( Y , w ) (Y,w) ( Y , w ) ( T , u ′ ) (T,u') ( T , u ′ ) σ : Y → T \sigma: Y \to T σ : Y → T σ \sigma σ ϕ = σ ∘ π : X → T \phi= \sigma\circ\pi: X \to T ϕ = σ ∘ π : X → T ϕ \phi ϕ
ε 10 + ( 1 + ε 10 ) ε 10 < ε . \frac{\varepsilon}{10}+\left(1+\frac{\varepsilon}{10}\right)\frac{\varepsilon}{10}<\varepsilon. 10 ε + ( 1 + 10 ε ) 10 ε < ε . Thus ϕ \phi ϕ
Since T ⊆ Y ⊆ X T \subseteq Y \subseteq X T ⊆ Y ⊆ X ν : X → T \nu: X \to T ν : X → T u ( t ) = ∣ ν − 1 ( t ) ∣ u(t)=|\nu^{-1}(t)| u ( t ) = ∣ ν − 1 ( t ) ∣ ϕ ( x ) ∈ T \phi(x)\in T ϕ ( x ) ∈ T x ∈ X x\in X x ∈ X
dist ( x , ν ( x ) ) ≤ dist ( x , ϕ ( x ) ) . \operatorname{dist}(x,\nu(x))\leq\operatorname{dist}(x,\phi(x)). dist ( x , ν ( x )) ≤ dist ( x , ϕ ( x )) . Hence, by Lemma 5.11, ( T , u ) (T,u) ( T , u ) ε \varepsilon ε X X X ν \nu ν ( Y , w ) (Y,w) ( Y , w ) n n n
Running Time
The direct density-adaptive implementation computes all pairwise distances and therefore takes O ( n 2 log n ) O(n^2\log n) O ( n 2 log n )
Let M = ∣ Y ∣ M=|Y| M = ∣ Y ∣ M ≤ ( k ε ) O ( d d i m ) log n M\leq\left(\frac{k}{\varepsilon}\right)^{O(\mathrm{ddim})}\log n M ≤ ( ε k ) O ( ddim ) log n
Lemma 4.16 computes the weighted density values in O ( M 2 ( log M + log n ) ) O(M^2(\log M+\log n)) O ( M 2 ( log M + log n )) ( k ε ) O ( d d i m ) polylog n \left(\frac{k}{\varepsilon}\right)^{O(\mathrm{ddim})}\operatorname{polylog} n ( ε k ) O ( ddim ) polylog n
Together with the near-linear annular construction and the Czumaj–Sohler polylogarithmic-factor approximation algorithm, this gives a randomized near-linear-time implementation in the original input size n n n
Proof of the Density-Adaptive Coreset Theorem
Theorem 1.4 (Density-adaptive coreset). Let ( X , dist ) (X,\operatorname{dist}) ( X , dist ) n n n d d i m ≥ 1 \mathrm{ddim}\geq1 ddim ≥ 1 0 < ε < 1 2 0<\varepsilon<\frac{1}{2} 0 < ε < 2 1 ε \varepsilon ε ( S , w ) (S,w) ( S , w )
∣ S ∣ ≤ ( 1 ε ) O ( d d i m ) k log n , |S|\leq\left(\frac{1}{\varepsilon}\right)^{O(\mathrm{ddim})}k\log n, ∣ S ∣ ≤ ( ε 1 ) O ( ddim ) k log n , whose movement rule is the nearest-neighbor map. Moreover, such a coreset can be constructed in randomized near-linear time with high probability.
Proof. The existential statement follows from the density-adaptive construction analyzed above, using any value O P T \mathrm{OPT} OPT O P T ≤ O P T ^ ≤ O ( O P T ) \mathrm{OPT}\leq\widehat{\mathrm{OPT}}\leq O(\mathrm{OPT}) OPT ≤ OPT ≤ O ( OPT ) ε \varepsilon ε
k ( 1 ε ) O ( d d i m ) log n . k\left(\frac{1}{\varepsilon}\right)^{O(\mathrm{ddim})}\log n. k ( ε 1 ) O ( ddim ) log n . For the randomized implementation, run the polylogarithmic-factor approximation algorithm of Czumaj and Sohler [12 ] , and let A A A 2 OPT ≤ A ≤ 2 L OPT 2\operatorname{OPT} \le A \le2L\operatorname{OPT} 2 OPT ≤ A ≤ 2 L OPT L = ( log n ) O ( 1 ) L = (\log n)^{O(1)} L = ( log n ) O ( 1 ) ( ε / 20 ) (\varepsilon/20) ( ε /20 ) ( Y , w ) (Y,w) ( Y , w ) X X X ( Y , w ) (Y,w) ( Y , w ) ( ε / 20 ) (\varepsilon/20) ( ε /20 ) ε < 1 / 2 \varepsilon< 1/2 ε < 1/2
OPT Y , w ≤ A ≤ 4 OPT Y , w . \operatorname{OPT}_{Y,w} \le A \le4\operatorname{OPT}_{Y,w}. OPT Y , w ≤ A ≤ 4 OPT Y , w . For i = 0 , … , ⌈ log 2 ( 4 L ) ⌉ i = 0,\ldots,\lceil\log_2(4L)\rceil i = 0 , … , ⌈ log 2 ( 4 L )⌉ A i = A / 2 i A_i = A/2^i A i = A / 2 i ( Y , w ) (Y,w) ( Y , w ) A i A_i A i ε / 20 \varepsilon/20 ε /20 Lemma 4.15 for a universal constant c c c T T T j j j i ⋆ i^\star i ⋆ OPT Y , w ≤ A i ⋆ < 2 OPT Y , w \operatorname{OPT}_{Y,w} \le A_{i^\star} < 2\operatorname{OPT}_{Y,w} OPT Y , w ≤ A i ⋆ < 2 OPT Y , w Lemma 4.15 , this run meets the size bound and is therefore not discarded. Hence j ≥ i ⋆ j \ge i^\star j ≥ i ⋆ A j < 2 OPT Y , w A_j < 2\operatorname{OPT}_{Y,w} A j < 2 OPT Y , w Lemma 4.11 uses only this upper bound, so its bound also holds for the selected run. The lower bound on the estimate is needed only for Lemma 4.14 ; here, the size bound holds by the choice of T T T Lemma 5.10 and Lemma 5.11 gives, after reweighting, an ε \varepsilon ε X X X n n n ( k / ε ) O ( d d i m ) log n (k/\varepsilon)^{O(\mathrm{ddim})}\log n ( k / ε ) O ( ddim ) log n O ( log L ) O(\log L) O ( log L ) ( k / ε ) O ( d d i m ) polylog n (k/\varepsilon)^{O(\mathrm{ddim})}\operatorname{polylog} n ( k / ε ) O ( ddim ) polylog n n n n
A Lower Bound for Movement Coresets
We next show that the logarithmic dependence on n n n k = 2 k = 2 k = 2 k k k n n n [7 ] .
Proposition 4.18 (A logarithmic lower bound for movement coresets). There are one-dimensional Euclidean instances of constant doubling dimension for which every 1 / 100 1/100 1/100 2 2 2 Ω ( log n ) \Omega(\log n) Ω ( log n ) n n n
Proof. Let M M M
L = ⌊ 1 2 log 2 M ⌋ , r i = 2 − i , L = \left\lfloor\frac{1}{2}\log_2 M \right\rfloor,\qquad r_i = 2^{-i}, L = ⌊ 2 1 log 2 M ⌋ , r i = 2 − i , and consider the multiset
X = { 0 d } M ∪ { x i = r i e 1 : i ∈ [ L ] } . X = \{0_d\}^{M} \cup\{x_i = r_i e_1 : i \in[L]\}. X = { 0 d } M ∪ { x i = r i e 1 : i ∈ [ L ]} . This instance lies on a line, hence has constant doubling dimension, and its size is M + L = Θ ( M ) M + L = \Theta(M) M + L = Θ ( M ) ( S , w ) (S,w) ( S , w ) ∣ S ∣ < L |S| < L ∣ S ∣ < L 2 2 2 π \pi π
First, all copies of 0 d 0_d 0 d π \pi π L 2 L^2 L 2 2 ( M − 1 ) 2 − L 2(M-1)2^{-L} 2 ( M − 1 ) 2 − L M M M z ∈ S z \in S z ∈ S
We now look at the distance from each representative π ( x i ) \pi(x_i) π ( x i ) z z z i i i dist ( x i , 0 d ) = r i \operatorname{dist}(x_i,0_d) = r_i dist ( x i , 0 d ) = r i r i / 4 r_i/4 r i /4 i i i
dist ( π ( x i ) , z ) ∈ [ 3 4 r i , 5 4 r i ] . \operatorname{dist}(\pi(x_i),z) \in\left[\frac{3}{4}r_i,\frac{5}{4}r_i\right]. dist ( π ( x i ) , z ) ∈ [ 4 3 r i , 4 5 r i ] . These intervals are disjoint: for consecutive radii, 5 4 r i + 1 = 5 8 r i < 3 4 r i \frac{5}{4}r_{i+1}=\frac{5}{8}r_i<\frac{3}{4}r_i 4 5 r i + 1 = 8 5 r i < 4 3 r i L L L dist ( π ( x i ) , z ) \operatorname{dist}(\pi(x_i),z) dist ( π ( x i ) , z ) π ( x i ) \pi(x_i) π ( x i ) L L L S S S ∣ S ∣ < L |S|<L ∣ S ∣ < L i ∈ [ L ] i\in[L] i ∈ [ L ]
∣ dist ( π ( x i ) , z ) − r i ∣ > 1 4 r i . \left|\operatorname{dist}(\pi(x_i),z)-r_i\right|>\frac{1}{4}r_i. ∣ dist ( π ( x i ) , z ) − r i ∣ > 4 1 r i . Consider the 2-partition P i = { A i , B i } P_i=\{A_i,B_i\} P i = { A i , B i }
A i = { 0 d } M ∪ { x i } , B i = X ∖ A i . A_i=\{0_d\}^{M}\cup\{x_i\},\qquad B_i=X\setminus A_i. A i = { 0 d } M ∪ { x i } , B i = X ∖ A i . The contribution of A i A_i A i 2 M r i 2Mr_i 2 M r i π \pi π 2 M dist ( π ( x i ) , z ) 2M\operatorname{dist}(\pi(x_i),z) 2 M dist ( π ( x i ) , z ) M r i / 2 Mr_i/2 M r i /2 B i B_i B i L 2 L^2 L 2 B i B_i B i L L L
∣ cost ( P i ) − cost ( π ( P i ) ) ∣ ≥ 1 2 M r i − 2 L 2 . \left|\operatorname{cost}(P_i)-\operatorname{cost}(\pi(P_i))\right|\ge\frac{1}{2}Mr_i-2L^2. ∣ cost ( P i ) − cost ( π ( P i )) ∣ ≥ 2 1 M r i − 2 L 2 . As i ≤ L i\le L i ≤ L M r i ≥ M 2 − L ≥ M Mr_i\ge M2^{-L}\ge\sqrt{M} M r i ≥ M 2 − L ≥ M M M M M r i / 4 Mr_i/4 M r i /4
cost ( P i ) ≤ 2 M r i + L 2 ≤ 3 M r i . \operatorname{cost}(P_i)\le2Mr_i+L^2\le3Mr_i. cost ( P i ) ≤ 2 M r i + L 2 ≤ 3 M r i . The relative error is therefore at least 1 / 12 1/12 1/12 1 / 100 1/100 1/100 L = Θ ( log ∣ X ∣ ) L=\Theta(\log|X|) L = Θ ( log ∣ X ∣ )
Streaming Applications
The coreset constructions also imply two streaming applications. For insertion-only streams, we combine the two-pass streaming algorithm of Czumaj and Sohler [12 ] with the annular construction. The annular construction also gives a multipass dynamic streaming algorithm by repeatedly improving a coarse reference solution and then building the final coreset.
Corollary 1.5 (Algorithm for insertion-only streams). There is a randomized three-pass algorithm for insertion-only streams that, given as input an n n n ( X , dist ) (X,\operatorname{dist}) ( X , dist ) ddim ≥ 1 \operatorname{ddim}\ge1 ddim ≥ 1 0 < ε < 1 10 0<\varepsilon<\frac{1}{10} 0 < ε < 10 1 OPT ^ ∈ ( 1 ± ε ) OPT ( X ) \widehat{\operatorname{OPT}}\in(1\pm\varepsilon)\operatorname{OPT}(X) OPT ∈ ( 1 ± ε ) OPT ( X ) ( k log n ) O ( 1 ) + ( k ε ) O ( ddim ) log n (k\log n)^{O(1)}+\left(\frac{k}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n ( k log n ) O ( 1 ) + ( ε k ) O ( ddim ) log n 2 Moreover, with one additional pass, the algorithm can output a k k k X X X 1 + ε 1+\varepsilon 1 + ε
Proof. Run the two-pass streaming algorithm of Czumaj and Sohler [12 ] . It returns a constant-factor solution for balanced k k k k k k c 1 , … , c k c_1,\ldots,c_k c 1 , … , c k c OPT c\operatorname{OPT} c OPT c > 0 c>0 c > 0
In a third pass, run the annular construction with this reference solution, using the cost of the reference solution as the reference cost, and using the same radius sequence, terminal level, and accuracy parameter, with c c c Lemma 4.3 . The representatives and weights are maintained online; the induced online movement rule is used only in the analysis of the value estimate. For every center c i c_i c i j j j η r j \eta r_j η r j N i , j ⊆ X ∩ B ( c i , r j ) N_{i,j} \subseteq X \cap B(c_i,r_j) N i , j ⊆ X ∩ B ( c i , r j ) x x x c i c_i c i x x x ℓ i ( x ) \ell_i(x) ℓ i ( x ) x x x N i , ℓ i ( x ) N_{i,\ell_i(x)} N i , ℓ i ( x ) x x x x x x 1 1 1 x x x s s s S S S w ′ w' w ′
For the analysis, let π ′ : X → S \pi': X \to S π ′ : X → S s s s s s s
∀ s ∈ S w ′ ( s ) = ∣ ( π ′ ) − 1 ( s ) ∣ . \forall s \in S \qquad w'(s) = \left|(\pi')^{-1}(s)\right|. ∀ s ∈ S w ′ ( s ) = ( π ′ ) − 1 ( s ) . Under this implicit rule, a point that creates a representative incurs zero movement, and every other point is sent to a representative that covers it at the annular level of a closest reference center. Hence the movement bound of Lemma 4.2 holds for π ′ \pi' π ′ Lemma 4.3 applies unchanged. Thus ( S , w ′ ) (S,w') ( S , w ′ ) π ′ \pi' π ′ ε \varepsilon ε
The algorithm then computes the optimal weighted min-sum value on ( S , w ′ ) (S,w') ( S , w ′ ) O P T ^ \widehat{\mathrm{OPT}} OPT ( 1 ± ε ) (1 \pm\varepsilon) ( 1 ± ε ) Corollary 5.3 , there is a partition of S S S ( 1 + ε ) O P T (1+\varepsilon)\mathrm{OPT} ( 1 + ε ) OPT
O P T ^ ≤ ( 1 + ε ) O P T . \widehat{\mathrm{OPT}} \le(1+\varepsilon)\mathrm{OPT}. OPT ≤ ( 1 + ε ) OPT . Conversely, let Q Q Q ( S , w ′ ) (S,w') ( S , w ′ ) P P P X X X π ′ \pi' π ′ cost S , w ′ ( Q ) = cost ( π ′ ( P ) ) \operatorname{cost}_{S,w'}(Q)=\operatorname{cost}(\pi'(P)) cost S , w ′ ( Q ) = cost ( π ′ ( P ))
O P T ^ = cost S , w ′ ( Q ) ≥ ( 1 − ε ) cost ( P ) ≥ ( 1 − ε ) O P T . \widehat{\mathrm{OPT}}=\operatorname{cost}_{S,w'}(Q)\ge(1-\varepsilon)\operatorname{cost}(P)\ge(1-\varepsilon)\mathrm{OPT}. OPT = cost S , w ′ ( Q ) ≥ ( 1 − ε ) cost ( P ) ≥ ( 1 − ε ) OPT . With one additional pass over the stream, keep the same representative set S S S π : X → S \pi:X\to S π : X → S w ( s ) = ∣ π − 1 ( s ) ∣ w(s)=|\pi^{-1}(s)| w ( s ) = ∣ π − 1 ( s ) ∣ π ( x ) \pi(x) π ( x ) S S S π ′ ( x ) ∈ S \pi'(x)\in S π ′ ( x ) ∈ S dist ( x , π ( x ) ) ≤ dist ( x , π ′ ( x ) ) \operatorname{dist}(x,\pi(x))\le\operatorname{dist}(x,\pi'(x)) dist ( x , π ( x )) ≤ dist ( x , π ′ ( x )) x ∈ X x\in X x ∈ X π \pi π Lemma 5.11 , the bound in Lemma 4.3 applies to the recounted weighted set ( S , w ) (S,w) ( S , w )
Since each N i , j N_{i,j} N i , j η r j \eta r_j η r j B ( c i , r j ) B(c_i,r_j) B ( c i , r j ) Lemma 4.5 gives
∣ S ∣ ≤ ( k ε ) O ( ddim ) log n . |S| \le\left(\frac{k}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n. ∣ S ∣ ≤ ( ε k ) O ( ddim ) log n . Adding the poly ( k , log n ) \operatorname{poly}(k,\log n) poly ( k , log n )
Grid version of the annular construction. For the dynamic and Euclidean setting we use the same annular construction, but replace the nets by fixed grids. This makes the set of possible representatives independent of the active point set, which is necessary when points may later be deleted.
Let
R = { R 1 , … , R k } \mathcal{R}=\{R_1,\ldots,R_k\} R = { R 1 , … , R k } be a reference partition with centers c 1 , … , c k c_1,\ldots,c_k c 1 , … , c k O P T ^ = cost ( R ) \widehat{\mathrm{OPT}}=\operatorname{cost}(\mathcal{R}) OPT = cost ( R )
r 0 = 20 O P T ^ , r j = r 0 2 j , j = 0 , … , L , r_0=20\widehat{\mathrm{OPT}},\qquad r_j=\frac{r_0}{2^j},\qquad j=0,\ldots,L, r 0 = 20 OPT , r j = 2 j r 0 , j = 0 , … , L , where L = ⌈ log 2 ( 40 n 10 ) ⌉ L=\lceil\log_2(40n^{10})\rceil L = ⌈ log 2 ( 40 n 10 )⌉ i ∈ [ k ] i\in[k] i ∈ [ k ] j j j c i c_i c i
ℓ j = ε r j d . \ell_j=\frac{\varepsilon r_j}{\sqrt{d}}. ℓ j = d ε r j . Let S S S B ( c i , r j ) B(c_i,r_j) B ( c i , r j ) i i i j j j π : X → S \pi:X\to S π : X → S x ∈ X x\in X x ∈ X π ( x ) ∈ S \pi(x)\in S π ( x ) ∈ S
The same movement bound as in the annular construction holds. Consequently, all pairwise movement estimates from the annular proof remain unchanged. The only difference is the size bound. At each level and for each center, the number of grid points is at most
( C k d ε ) d \left(\frac{Ck\sqrt{d}}{\varepsilon}\right)^d ( ε C k d ) d for a universal constant C C C
∣ S ∣ ≤ k ( C k d ε ) d log n . |S|\leq k\left(\frac{Ck\sqrt{d}}{\varepsilon}\right)^d\log n. ∣ S ∣ ≤ k ( ε C k d ) d log n . The advantage of this grid version is that insertions and deletions only change the weights of fixed representatives: an insertion increases the weight of π ( x ) \pi(x) π ( x )
Corollary 1.6 (Algorithm for dynamic Euclidean streams). There is a randomized multipass algorithm for dynamic streams that, given as input an n n n X ⊆ [ Δ ] d X\subseteq[\Delta]^d X ⊆ [ Δ ] d Δ = poly ( n ) \Delta=\operatorname{poly}(n) Δ = poly ( n ) ddim ≥ 1 \operatorname{ddim}\geq1 ddim ≥ 1 0 < ε < 1 10 0<\varepsilon<\frac{1}{10} 0 < ε < 10 1 3 / 4 3/4 3/4 O P T ^ ∈ ( 1 ± ε ) OPT ( X ) \widehat{\mathrm{OPT}}\in(1\pm\varepsilon)\operatorname{OPT}(X) OPT ∈ ( 1 ± ε ) OPT ( X ) O ( log n ) O(\log n) O ( log n ) ( k t / ε ) d log n + poly ( d , k , t , log log ( n Δ ) ) (kt/\varepsilon)^d\log n+\operatorname{poly}(d,k,t,\log\log(n\Delta)) ( k t / ε ) d log n + poly ( d , k , t , log log ( n Δ )) t = O ( ε − 2 ( ddim log ( 1 / ε ) + log k + log log n ) ) t=O(\varepsilon^{-2}(\operatorname{ddim}\log(1/\varepsilon)+\log k+\log\log n)) t = O ( ε − 2 ( ddim log ( 1/ ε ) + log k + log log n ))
Moreover, with one additional pass, the algorithm can output a k k k X X X 1 + ε 1+\varepsilon 1 + ε
Proof. We first apply the dynamic k k k [7 ] to the original stream on [ Δ ] d [\Delta]^d [ Δ ] d k k k C = { c 1 , … , c k } C=\{c_1,\ldots,c_k\} C = { c 1 , … , c k } D D D k k k X X X D ≤ O ( 1 ) OPT m e d ≤ O ( 1 ) OPT D\leq O(1)\operatorname{OPT}_{\mathrm{med}}\leq O(1)\operatorname{OPT} D ≤ O ( 1 ) OPT med ≤ O ( 1 ) OPT
We now choose the Gaussian map f f f
t = O ( ε − 2 ( ddim log ( 1 / ε ) + log k + log log n ) ) . t=O\left(\varepsilon^{-2}(\operatorname{ddim}\log(1/\varepsilon)+\log k+\log\log n)\right). t = O ( ε − 2 ( ddim log ( 1/ ε ) + log k + log log n ) ) . For each x ∈ X x\in X x ∈ X σ ( x ) ∈ C \sigma(x)\in C σ ( x ) ∈ C x x x C C C σ \sigma σ f f f
∑ x ∈ X ∥ f ( x ) − f ( σ ( x ) ) ∥ ≤ O ( 1 ) ∑ x ∈ X ∥ x − σ ( x ) ∥ ≤ O ( n D ) . \sum_{x\in X}\|f(x)-f(\sigma(x))\|\leq O(1)\sum_{x\in X}\|x-\sigma(x)\|\leq O(nD). x ∈ X ∑ ∥ f ( x ) − f ( σ ( x )) ∥ ≤ O ( 1 ) x ∈ X ∑ ∥ x − σ ( x ) ∥ ≤ O ( n D ) . Thus the projected centers f ( C ) f(C) f ( C ) k k k O ( n D ) O(nD) O ( n D ) P 0 \mathcal{P}_0 P 0 f ( X ) f(X) f ( X ) f ( C ) f(C) f ( C )
cost ( P 0 ) ≤ 2 n ∑ x ∈ X dist ( f ( x ) , f ( C ) ) ≤ O ( n 2 D ) ≤ O ( n 2 ) OPT . \operatorname{cost}(\mathcal{P}_0)\leq2n\sum_{x\in X}\operatorname{dist}(f(x),f(C))\leq O(n^2D)\leq O(n^2)\operatorname{OPT}. cost ( P 0 ) ≤ 2 n x ∈ X ∑ dist ( f ( x ) , f ( C )) ≤ O ( n 2 D ) ≤ O ( n 2 ) OPT . By Theorem 1.2, the optimum min-sum cost in the embedded instance is within a constant factor of OPT. Hence f ( C ) f(C) f ( C ) R t \mathbb{R}^{t} R t k k k [ Δ ] d [\Delta]^{d} [ Δ ] d R t \mathbb{R}^{t} R t
The movement inequalities imply an improvement recurrence of the form
cost ( P r + 1 ) ≤ O ( 1 ) OPT + 1 2 cost ( P r ) . \operatorname{cost}(\mathcal{P}_{r+1}) \le O(1)\operatorname{OPT} + \frac{1}{2}\operatorname{cost}(\mathcal{P}_{r}). cost ( P r + 1 ) ≤ O ( 1 ) OPT + 2 1 cost ( P r ) . After O ( log n ) O(\log n) O ( log n )
In one additional pass, run the same grid construction with movement parameter
η = Θ ( ε k ) . \eta= \Theta\left(\frac{\varepsilon}{k}\right). η = Θ ( k ε ) . The movement guarantee then gives, for every partition P \mathcal{P} P X X X k k k
∣ cost ( P ) − cost ( π ( P ) ) ∣ ≤ ε cost ( P ) . \left|\operatorname{cost}(\mathcal{P})-\operatorname{cost}(\pi(\mathcal{P}))\right| \le\varepsilon\operatorname{cost}(\mathcal{P}). ∣ cost ( P ) − cost ( π ( P )) ∣ ≤ ε cost ( P ) . Since the grid construction is now applied in dimension t t t
( C k t ε ) t \left(\frac{Ck\sqrt{t}}{\varepsilon}\right)^{t} ( ε C k t ) t representatives per center and per level. There are k k k O ( log n ) O(\log n) O ( log n )
k ( C k t ε ) t log n . k\left(\frac{Ck\sqrt{t}}{\varepsilon}\right)^{t}\log n. k ( ε C k t ) t log n . After adjusting the constant hidden in the definition of t t t
( k t ε ) t log n . \left(\frac{kt}{\varepsilon}\right)^{t}\log n. ( ε k t ) t log n . Together with the initial constant-factor k k k O ( log n ) O(\log n) O ( log n )
poly ( d , k , log ( n ) ) + ( k t ε ) t log n . \operatorname{poly}(d,k,\log(n))+\left(\frac{kt}{\varepsilon}\right)^{t}\log n. poly ( d , k , log ( n )) + ( ε k t ) t log n . As in the insertion-only case, solving the final weighted instance gives a value OPT ^ ∈ ( 1 ± ε ) OPT \widehat{\operatorname{OPT}}\in(1\pm\varepsilon)\operatorname{OPT} OPT ∈ ( 1 ± ε ) OPT X X X π \pi π k k k P ^ \widehat{\mathcal{P}} P cost ( P ^ ) ≤ ( 1 + O ( ε ) ) OPT \operatorname{cost}(\widehat{\mathcal{P}})\le(1+O(\varepsilon))\operatorname{OPT} cost ( P ) ≤ ( 1 + O ( ε )) OPT ε \varepsilon ε
Coreset Properties
Movement coresets compress the input while approximately preserving the cost of every partition. This raises several questions beyond their construction: whether optimization can be performed directly on the weighted instance, whether the same constructions extend to related objectives, and whether the guarantees remain valid when coresets or movement rules are combined. The results in this section demonstrate that movement-coresets support substantially more than partition-cost preservation.
Our results in this section rely on two different coreset guarantees. Some use only the fact that the cost of every partition is preserved, whereas others require explicit control of the movement (distances between input points and their representatives). Since a point x x x A A A ∣ A ∣ − 1 |A|-1 ∣ A ∣ − 1 ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) \lvert A\rvert\sum_{x\in A}\operatorname{dist}(x,\pi(x)) ∣ A ∣ ∑ x ∈ A dist ( x , π ( x )) ϵ \epsilon ϵ Claim 5.2 and Corollary 5.3 ), extend the constructions to related objectives (Lemma 5.4 and Proposition 5.6 ), and determine when coresets can be combined or reweighted without losing their guarantees (Lemma 5.8 , Lemma 5.9 and Lemma 5.11 ).
Definition 5.1 (Bounded-movement coreset). A weighted set ( S , w ) (S,w) ( S , w ) S ⊂ X S\subset X S ⊂ X ϵ \epsilon ϵ π : X → S \pi:X\to S π : X → S k k k P \mathcal{P} P X X X
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) ≤ ϵ ⋅ cost ( P ) . (37) \sum_{A\in\mathcal{P}} |A|\sum_{x\in A}\operatorname{dist}(x,\pi(x)) \le\epsilon\cdot\operatorname{cost}(\mathcal{P}). \tag*{(37)} A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) ≤ ϵ ⋅ cost ( P ) . (37) It is sometimes useful to restrict this requirement to a specified set of feasible partitions.
This bound controls, for every partition, the distances between the input points and their representatives relative to the cost of the partition. By the triangle inequality, every ϵ \epsilon ϵ 2 ϵ 2\epsilon 2 ϵ
Unsplitting and Optimization
A k k k ( S , w ) (S,w) ( S , w ) s ∈ S s\in S s ∈ S S S S
Claim 5.2 (Unsplitting representatives). Let ( S , w ) (S,w) ( S , w ) ( S , w ) (S,w) ( S , w ) k k k s ∈ S s\in S s ∈ S k k k
Proof. If the copies of some s ∈ S s\in S s ∈ S s s s s s s S S S
Consequently, optimizing over consistent partitions of ( S , w ) (S,w) ( S , w ) X X X k k k X X X
Corollary 5.3 (Optimization on a movement coreset). Let ( S , w ) (S,w) ( S , w ) ϵ \epsilon ϵ π : X → S \pi:X\to S π : X → S Q ∗ Q^* Q ∗ S S S k k k
cost S , w ( Q ∗ ) ≤ ( 1 + ϵ ) OPT . \operatorname{cost}_{S,w}(Q^*)\le(1+\epsilon)\operatorname{OPT}. cost S , w ( Q ∗ ) ≤ ( 1 + ϵ ) OPT . Proof. Let P ∗ \mathcal{P}^* P ∗ X X X π ( P ∗ ) \pi(\mathcal{P}^*) π ( P ∗ ) S S S k k k π ( P ∗ ) \pi(\mathcal{P}^*) π ( P ∗ ) ( 1 + ε ) O P T (1+\varepsilon)\mathrm{OPT} ( 1 + ε ) OPT Claim 5.2 , we may consolidate the copies of every representative without increasing the cost, which gives the desired weighted partition of S S S
Costs with Powers of Distances
Fix a constant z ≥ 1 z \ge1 z ≥ 1 A ⊆ X A \subseteq X A ⊆ X P \mathcal{P} P X X X
cost z ( A ) = ∑ x , y ∈ A dist ( x , y ) z , cost z ( P ) = ∑ A ∈ P cost z ( A ) , O P T z = min P cost z ( P ) . \operatorname{cost}_z(A)=\sum_{x,y\in A}\operatorname{dist}(x,y)^z,\qquad\operatorname{cost}_z(\mathcal{P})=\sum_{A\in\mathcal{P}}\operatorname{cost}_z(A),\qquad\mathrm{OPT}_z=\min_{\mathcal{P}}\operatorname{cost}_z(\mathcal{P}). cost z ( A ) = x , y ∈ A ∑ dist ( x , y ) z , cost z ( P ) = A ∈ P ∑ cost z ( A ) , OPT z = P min cost z ( P ) . In this subsection, we use the power-z z z Definition 5.1 which is obtained by raising each movement distance to power z z z cost z \operatorname{cost}_z cost z
Lemma 5.4 (Density-adaptive coresets for distance powers). For every z ≥ 1 z \ge1 z ≥ 1 0 < ε < 1 / 2 0 < \varepsilon< 1/2 0 < ε < 1/2
k ( z ε ) O ( ddim ) log n k\left(\frac{z}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n k ( ε z ) O ( ddim ) log n whose movement rule π \pi π k k k P \mathcal{P} P
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z ≤ ( ε 16 z ) z cost z ( P ) . \sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(x,\pi(x))^z\le\left(\frac{\varepsilon}{16z}\right)^z\operatorname{cost}_z(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z ≤ ( 16 z ε ) z cost z ( P ) . Thus, the resulting coreset satisfies the power-z z z Definition 5.1 with ε ′ = ( ε / ( 16 z ) ) z \varepsilon'=(\varepsilon/(16z))^z ε ′ = ( ε / ( 16 z ) ) z cost z \operatorname{cost}_z cost z 1 ± ε 1\pm\varepsilon 1 ± ε k k k
Proof. In the density-adaptive construction, replace the movement scale by
r ( x ) = min 2 ≤ m ≤ n max { ( 1 m ∑ w ∈ Γ m ( x ) dist ( x , w ) z ) 1 / z , ( O P T ^ z k m 2 ) 1 / z } . r(x)=\min_{2\le m\le n}\max\left\{\left(\frac{1}{m}\sum_{w\in\Gamma_m(x)}\operatorname{dist}(x,w)^z\right)^{1/z},\left(\frac{\widehat{\mathrm{OPT}}_z}{km^2}\right)^{1/z}\right\}. r ( x ) = 2 ≤ m ≤ n min max ⎩ ⎨ ⎧ m 1 w ∈ Γ m ( x ) ∑ dist ( x , w ) z 1/ z , ( k m 2 OPT z ) 1/ z ⎭ ⎬ ⎫ . where O P T z ≤ O P T ^ z ≤ C ⋅ O P T z \mathrm{OPT}_z\le\widehat{\mathrm{OPT}}_z\le C\cdot\mathrm{OPT}_z OPT z ≤ OPT z ≤ C ⋅ OPT z C ≥ 1 C\ge1 C ≥ 1 η r ( x ) \eta r(x) η r ( x ) η = ε / ( 32 C z ) \eta=\varepsilon/(32Cz) η = ε / ( 32 C z ) S r S_r S r { x ∈ X : r ≤ r ( x ) < 2 r } \{x\in X:r\le r(x)<2r\} { x ∈ X : r ≤ r ( x ) < 2 r } S S S ∣ A ∣ = m |A|=m ∣ A ∣ = m r ( x ) r(x) r ( x )
∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z ≤ η z cost z ( A ) + η z O P T ^ z k . |A|\sum_{x\in A}\operatorname{dist}(x,\pi(x))^z\le\eta^z\operatorname{cost}_z(A)+\frac{\eta^z\widehat{\mathrm{OPT}}_z}{k}. ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z ≤ η z cost z ( A ) + k η z OPT z . Summing over the at most k k k P \mathcal{P} P O P T ^ z ≤ C ⋅ O P T z ≤ C ⋅ cost z ( P ) \widehat{\mathrm{OPT}}_z\le C\cdot\mathrm{OPT}_z\le C\cdot\operatorname{cost}_z(\mathcal{P}) OPT z ≤ C ⋅ OPT z ≤ C ⋅ cost z ( P )
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z ≤ ( 1 + C ) η z cost z ( P ) ≤ ( ε 16 z ) z cost z ( P ) . \sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(x,\pi(x))^z\le(1+C)\eta^z\operatorname{cost}_z(\mathcal{P})\le\left(\frac{\varepsilon}{16z}\right)^z\operatorname{cost}_z(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z ≤ ( 1 + C ) η z cost z ( P ) ≤ ( 16 z ε ) z cost z ( P ) . This proves the displayed movement bound.
For all a , b ≥ 0 a,b\ge0 a , b ≥ 0
( a + b ) z ≤ ( 1 + ε 2 ) a z + ( 1 + 4 z ε ) z − 1 b z . (38) (a+b)^z\le\left(1+\frac{\varepsilon}{2}\right)a^z+\left(1+\frac{4z}{\varepsilon}\right)^{z-1}b^z. \tag*{(38)} ( a + b ) z ≤ ( 1 + 2 ε ) a z + ( 1 + ε 4 z ) z − 1 b z . (38) For every part A ∈ P A \in\mathcal{P} A ∈ P x , y ∈ A x,y \in A x , y ∈ A
b x , y = dist ( x , π ( x ) ) + dist ( y , π ( y ) ) . b_{x,y}=\operatorname{dist}(x,\pi(x))+\operatorname{dist}(y,\pi(y)). b x , y = dist ( x , π ( x )) + dist ( y , π ( y )) . By the triangle inequality
∣ dist ( π ( x ) , π ( y ) ) − dist ( x , y ) ∣ ≤ b x , y . \left|\operatorname{dist}(\pi(x),\pi(y))-\operatorname{dist}(x,y)\right|\le b_{x,y}. ∣ dist ( π ( x ) , π ( y )) − dist ( x , y ) ∣ ≤ b x , y . Applying (38) gives
dist ( π ( x ) , π ( y ) ) z ≤ ( 1 + ε 2 ) dist ( x , y ) z + ( 1 + 4 z ε ) z − 1 b x , y z . (39) \operatorname{dist}(\pi(x),\pi(y))^{z}\le\left(1+\frac{\varepsilon}{2}\right)\operatorname{dist}(x,y)^{z}+\left(1+\frac{4z}{\varepsilon}\right)^{z-1}b_{x,y}^{z}. \tag*{(39)} dist ( π ( x ) , π ( y ) ) z ≤ ( 1 + 2 ε ) dist ( x , y ) z + ( 1 + ε 4 z ) z − 1 b x , y z . (39) dist ( x , y ) z ≤ ( 1 + ε 2 ) dist ( π ( x ) , π ( y ) ) z + ( 1 + 4 z ε ) z − 1 b x , y z . (40) \operatorname{dist}(x,y)^{z}\le\left(1+\frac{\varepsilon}{2}\right)\operatorname{dist}(\pi(x),\pi(y))^{z}+\left(1+\frac{4z}{\varepsilon}\right)^{z-1}b_{x,y}^{z}. \tag*{(40)} dist ( x , y ) z ≤ ( 1 + 2 ε ) dist ( π ( x ) , π ( y ) ) z + ( 1 + ε 4 z ) z − 1 b x , y z . (40) We next bound the second term in these inequalities. Since
b x , y z ≤ 2 z − 1 ( dist ( x , π ( x ) ) z + dist ( y , π ( y ) ) z ) , b_{x,y}^{z}\le2^{z-1}\left(\operatorname{dist}(x,\pi(x))^{z}+\operatorname{dist}(y,\pi(y))^{z}\right), b x , y z ≤ 2 z − 1 ( dist ( x , π ( x ) ) z + dist ( y , π ( y ) ) z ) , summing over all pairs of points in all parts and rearranging gives
∑ A ∈ P ∑ x , y ∈ A b x , y z ≤ 2 z ∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z , \sum_{A\in\mathcal{P}}\sum_{x,y\in A}b_{x,y}^{z}\le2^{z}\sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(x,\pi(x))^{z}, A ∈ P ∑ x , y ∈ A ∑ b x , y z ≤ 2 z A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z , and since 1 + 4 z / ε ≤ 5 z / ε 1+4z/\varepsilon\le5z/\varepsilon 1 + 4 z / ε ≤ 5 z / ε
( 1 + 4 z ε ) z − 1 ∑ A ∈ P ∑ x , y ∈ A b x , y z ≤ 2 z ( 5 z ε ) z − 1 ( ε 16 z ) z cost z ( P ) ≤ ε 8 cost z ( P ) . \left(1+\frac{4z}{\varepsilon}\right)^{z-1}\sum_{A\in\mathcal{P}}\sum_{x,y\in A}b_{x,y}^{z}\le2^{z}\left(\frac{5z}{\varepsilon}\right)^{z-1}\left(\frac{\varepsilon}{16z}\right)^{z}\operatorname{cost}_{z}(\mathcal{P})\le\frac{\varepsilon}{8}\operatorname{cost}_{z}(\mathcal{P}). ( 1 + ε 4 z ) z − 1 A ∈ P ∑ x , y ∈ A ∑ b x , y z ≤ 2 z ( ε 5 z ) z − 1 ( 16 z ε ) z cost z ( P ) ≤ 8 ε cost z ( P ) . Summing (39) over all pairs gives
cost z ( π ( P ) ) ≤ ( 1 + ε 2 + ε 8 ) cost z ( P ) ≤ ( 1 + ε ) cost z ( P ) . \operatorname{cost}_{z}(\pi(\mathcal{P}))\le\left(1+\frac{\varepsilon}{2}+\frac{\varepsilon}{8}\right)\operatorname{cost}_{z}(\mathcal{P})\le(1+\varepsilon)\operatorname{cost}_{z}(\mathcal{P}). cost z ( π ( P )) ≤ ( 1 + 2 ε + 8 ε ) cost z ( P ) ≤ ( 1 + ε ) cost z ( P ) . Summing (40) over all pairs gives
cost z ( π ( P ) ) ≥ 1 − ε / 8 1 + ε / 2 cost z ( P ) ≥ ( 1 − ε ) cost z ( P ) . \operatorname{cost}_{z}(\pi(\mathcal{P}))\ge\frac{1-\varepsilon/8}{1+\varepsilon/2}\operatorname{cost}_{z}(\mathcal{P})\ge(1-\varepsilon)\operatorname{cost}_{z}(\mathcal{P}). cost z ( π ( P )) ≥ 1 + ε /2 1 − ε /8 cost z ( P ) ≥ ( 1 − ε ) cost z ( P ) . It remains to bound the size of S S S r r r N r N_r N r ( 16 r ) (16r) ( 16 r ) S r S_r S r z z z v ∈ N r v\in N_r v ∈ N r m v m_v m v B ( v , 4 r ) B(v,4r) B ( v , 4 r ) m v > OPT ^ z / ( 2 z k r z ) m_v>\sqrt{\widehat{\operatorname{OPT}}_z/(2^zkr^z)} m v > OPT z / ( 2 z k r z ) h = ⌈ OPT ^ z / ( 2 z + 2 k r z ) ⌉ h=\left\lceil\sqrt{\widehat{\operatorname{OPT}}_z/(2^{z+2}kr^z)}\right\rceil h = ⌈ OPT z / ( 2 z + 2 k r z ) ⌉ G v G_v G v z z z ∣ N r ∣ < 3 k |N_r|<3k ∣ N r ∣ < 3 k ( C z / ε ) O ( d d i m ) (Cz/\varepsilon)^{O(\mathrm{ddim})} ( C z / ε ) O ( ddim ) H H H k k k O ( log n ) O(\log n) O ( log n )
Lemma 5.5 (Annular coresets for power-z z z For every z ≥ 1 z\ge1 z ≥ 1 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2
( k z ε ) O ( d d i m ) log n \left(\frac{kz}{\varepsilon}\right)^{O(\mathrm{ddim})}\log n ( ε k z ) O ( ddim ) log n and satisfies, for every k k k P \mathcal{P} P
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z ≤ ( ε 16 z ) z cost z ( P ) . \sum_{A\in\mathcal{P}} |A|\sum_{x\in A} \operatorname{dist}(x,\pi(x))^{z} \le\left(\frac{\varepsilon}{16z}\right)^{z}\operatorname{cost}_{z}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z ≤ ( 16 z ε ) z cost z ( P ) . Thus it satisfies the power-z z z ε ′ = ( ε / ( 16 z ) ) z \varepsilon'=(\varepsilon/(16z))^{z} ε ′ = ( ε / ( 16 z ) ) z cost z \operatorname{cost}_{z} cost z 1 ± ε 1\pm\varepsilon 1 ± ε k k k
Proof. Run the annular construction with movement parameter η = ε / ( 16 C 0 z k ) \eta=\varepsilon/(16C_{0}zk) η = ε / ( 16 C 0 z k ) C 0 > 0 C_{0}>0 C 0 > 0 Lemma 4.4 , with every distance raised to the z z z z z z
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) z ≤ ( C 0 k η ) z cost z ( P ) = ( ε 16 z ) z cost z ( P ) . \sum_{A\in\mathcal{P}} |A|\sum_{x\in A} \operatorname{dist}(x,\pi(x))^{z} \le(C_{0}k\eta)^{z}\operatorname{cost}_{z}(\mathcal{P})=\left(\frac{\varepsilon}{16z}\right)^{z}\operatorname{cost}_{z}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x ) ) z ≤ ( C 0 k η ) z cost z ( P ) = ( 16 z ε ) z cost z ( P ) . As shown in the proof of Lemma 5.4 , this movement bound is sufficient to preserve cost z \operatorname{cost}_{z} cost z 1 ± ε 1\pm\varepsilon 1 ± ε
Balanced Euclidean k k k
The case z = 2 z=2 z = 2 k k k
For a k k k P \mathcal{P} P X X X C = ( c A ) A ∈ P C=(c_{A})_{A\in\mathcal{P}} C = ( c A ) A ∈ P k k k
cost b k m e a n s ( P , C ) = ∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , c A ) 2 . \operatorname{cost}_{\mathrm{bkmeans}}(\mathcal{P},C)=\sum_{A\in\mathcal{P}} |A|\sum_{x\in A}\operatorname{dist}(x,c_{A})^{2}. cost bkmeans ( P , C ) = A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , c A ) 2 . For a set B ⊆ R d B\subseteq\mathbb{R}^{d} B ⊆ R d
x ˉ B : = 1 ∣ B ∣ ∑ x ∈ B x . \bar{x}_{B}:=\frac{1}{|B|}\sum_{x\in B}x. x ˉ B := ∣ B ∣ 1 x ∈ B ∑ x . Let π : X → S \pi:X\to S π : X → S P \mathcal{P} P C = ( c A ) A ∈ P C=(c_{A})_{A\in\mathcal{P}} C = ( c A ) A ∈ P π \pi π
π ( C ) : = ( c A + x ˉ π ( A ) − x ˉ A ) A ∈ P . \pi(C):=\left(c_{A}+\bar{x}_{\pi(A)}-\bar{x}_{A}\right)_{A\in\mathcal{P}}. π ( C ) := ( c A + x ˉ π ( A ) − x ˉ A ) A ∈ P . We call ( S , w ) (S,w) ( S , w ) ε \varepsilon ε k k k k k k P \mathcal{P} P C = ( c A ) A ∈ P C=(c_{A})_{A\in\mathcal{P}} C = ( c A ) A ∈ P
cost b k m e a n s ( π ( P ) , π ( C ) ) ∈ ( 1 ± ε ) cost b k m e a n s ( P , C ) . \operatorname{cost}_{\mathrm{bkmeans}}(\pi(\mathcal{P}),\pi(C))\in(1\pm\varepsilon)\operatorname{cost}_{\mathrm{bkmeans}}(\mathcal{P},C). cost bkmeans ( π ( P ) , π ( C )) ∈ ( 1 ± ε ) cost bkmeans ( P , C ) . Proposition 5.6 (Preservation under shifted centers). Let X ⊆ R d X\subseteq\mathbb{R}^{d} X ⊆ R d 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 ( S , w ) (S,w) ( S , w ) ε \varepsilon ε cost 2 \operatorname{cost}_{2} cost 2 π : X → S \pi:X\to S π : X → S ( S , w ) (S,w) ( S , w ) ε \varepsilon ε k k k
Proof. For every A ∈ P A \in\mathcal{P} A ∈ P
∣ A ∣ ∑ x ∈ A dist ( x , c A ) 2 = 1 2 ∑ x , y ∈ A dist ( x , y ) 2 + ∣ A ∣ 2 dist ( x ˉ A , c A ) 2 . |A|\sum_{x\in A}\operatorname{dist}(x,c_A)^2=\frac{1}{2}\sum_{x,y\in A}\operatorname{dist}(x,y)^2+|A|^2\operatorname{dist}(\bar{x}_A,c_A)^2. ∣ A ∣ x ∈ A ∑ dist ( x , c A ) 2 = 2 1 x , y ∈ A ∑ dist ( x , y ) 2 + ∣ A ∣ 2 dist ( x ˉ A , c A ) 2 . and similarly, for the moved multiset π ( A ) \pi(A) π ( A )
∣ A ∣ ∑ x ∈ A dist ( π ( x ) , c A + x ˉ π ( A ) − x ˉ A ) 2 = 1 2 ∑ x , y ∈ A dist ( π ( x ) , π ( y ) ) 2 + ∣ A ∣ 2 dist ( x ˉ π ( A ) , c A + x ˉ π ( A ) − x ˉ A ) 2 . |A|\sum_{x\in A}\operatorname{dist}\left(\pi(x),c_A+\bar{x}_{\pi(A)}-\bar{x}_A\right)^2=\frac{1}{2}\sum_{x,y\in A}\operatorname{dist}(\pi(x),\pi(y))^2+|A|^2\operatorname{dist}\left(\bar{x}_{\pi(A)},c_A+\bar{x}_{\pi(A)}-\bar{x}_A\right)^2. ∣ A ∣ x ∈ A ∑ dist ( π ( x ) , c A + x ˉ π ( A ) − x ˉ A ) 2 = 2 1 x , y ∈ A ∑ dist ( π ( x ) , π ( y ) ) 2 + ∣ A ∣ 2 dist ( x ˉ π ( A ) , c A + x ˉ π ( A ) − x ˉ A ) 2 . Obviously,
x ˉ π ( A ) − ( c A + x ˉ π ( A ) − x ˉ A ) = x ˉ A − c A , \bar{x}_{\pi(A)}-\left(c_A+\bar{x}_{\pi(A)}-\bar{x}_A\right)=\bar{x}_A-c_A, x ˉ π ( A ) − ( c A + x ˉ π ( A ) − x ˉ A ) = x ˉ A − c A , and thus the last term in the two variance decompositions above has the same value. The proposition follows by summing over the parts and applying the movement-coreset guarantee for cost 2 \operatorname{cost}_2 cost 2
Corollary 5.7. (Density-adaptive coreset for balanced k k k For every Euclidean input X X X ε \varepsilon ε k k k P \mathcal{P} P C C C cost b k m e a n s ( P , C ) \operatorname{cost}_{\mathrm{bkmeans}}(\mathcal{P},C) cost bkmeans ( P , C ) 1 ± ε 1\pm\varepsilon 1 ± ε Proposition 5.6 , using k ( 1 ε ) O ( ddim ) log n k\left(\frac{1}{\varepsilon}\right)^{O(\operatorname{ddim})}\log n k ( ε 1 ) O ( ddim ) log n
Proof. The density-adaptive construction and analysis of Lemma 5.4 give the displayed movement guarantee and the stated size for balanced k k k Proposition 5.6 .
Color-Balanced Mergeability
A coreset construction is mergeable if coresets constructed independently for two sets can be combined into a coreset for their union. In general, movement coresets are not mergeable, because moving points from one set affects their distances to possibly many points from the other set. We show that merging is possible when every cluster contains the same number of points from the two sets. We call the points of the two sets red and blue and refer to such partitions as color-balanced.
Let R R R B B B X X X k k k X X X
Lemma 5.8. (Color-balanced mergeability). For each C ∈ { R , B } C \in\{R,B\} C ∈ { R , B } ( S C , w C ) (S_C,w_C) ( S C , w C ) ε \varepsilon ε C C C π C : C → S C \pi_C:C\to S_C π C : C → S C ( S , w ) (S,w) ( S , w ) w = w R + w B w=w_R+w_B w = w R + w B π : X → S \pi:X\to S π : X → S π ∣ C = π C \pi|_C=\pi_C π ∣ C = π C C ∈ { R , B } C\in\{R,B\} C ∈ { R , B } k k k P \mathcal{P} P X X X A ∈ P A\in\mathcal{P} A ∈ P ∣ A ∩ R ∣ = ∣ A ∩ B ∣ |A\cap R|=|A\cap B| ∣ A ∩ R ∣ = ∣ A ∩ B ∣
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) ≤ 2 ε cost ( P ) . \sum_{A\in\mathcal{P}} |A|\sum_{x\in A}\operatorname{dist}(x,\pi(x))\leq2\varepsilon\operatorname{cost}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) ≤ 2 ε cost ( P ) . Proof. Let P \mathcal{P} P k k k X X X
∀ A ∈ P ∣ A ∩ R ∣ = ∣ A ∩ B ∣ . \forall A\in\mathcal{P}\qquad|A\cap R|=|A\cap B|. ∀ A ∈ P ∣ A ∩ R ∣ = ∣ A ∩ B ∣. For each A ∈ P A\in\mathcal{P} A ∈ P
A R = A ∩ R , A B = A ∩ B . A_R=A\cap R,\qquad A_B=A\cap B. A R = A ∩ R , A B = A ∩ B . Color balance gives ∣ A ∣ = 2 ∣ A R ∣ = 2 ∣ A B ∣ |A|=2|A_R|=2|A_B| ∣ A ∣ = 2∣ A R ∣ = 2∣ A B ∣ P R = { A R ∣ A ∈ P } \mathcal{P}_R=\{A_R\mid A\in\mathcal{P}\} P R = { A R ∣ A ∈ P } P B = { A B ∣ A ∈ P } \mathcal{P}_B=\{A_B\mid A\in\mathcal{P}\} P B = { A B ∣ A ∈ P } A ∈ P A\in\mathcal{P} A ∈ P
cost ( A R ) + cost ( A B ) ≤ cost ( A ) \operatorname{cost}(A_R)+\operatorname{cost}(A_B)\leq\operatorname{cost}(A) cost ( A R ) + cost ( A B ) ≤ cost ( A ) Consequently,
cost ( P R ) + cost ( P B ) ≤ cost ( P ) . \operatorname{cost}(\mathcal{P}_R) + \operatorname{cost}(\mathcal{P}_B) \le\operatorname{cost}(\mathcal{P}). cost ( P R ) + cost ( P B ) ≤ cost ( P ) . Thus
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π ( x ) ) = 2 ∑ A ∈ P ( ∣ A R ∣ ∑ x ∈ A R dist ( x , π R ( x ) ) + ∣ A B ∣ ∑ x ∈ A B dist ( x , π B ( x ) ) ) \sum_{A\in\mathcal{P}} |A| \sum_{x\in A} \operatorname{dist}(x,\pi(x)) = 2 \sum_{A\in\mathcal{P}} \left( |A_R| \sum_{x\in A_R} \operatorname{dist}(x,\pi_R(x)) + |A_B| \sum_{x\in A_B} \operatorname{dist}(x,\pi_B(x)) \right) A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π ( x )) = 2 A ∈ P ∑ ( ∣ A R ∣ x ∈ A R ∑ dist ( x , π R ( x )) + ∣ A B ∣ x ∈ A B ∑ dist ( x , π B ( x )) ) ≤ 2 ε ( cost ( P R ) + cost ( P B ) ) \le2\varepsilon\left(\operatorname{cost}(\mathcal{P}_R) + \operatorname{cost}(\mathcal{P}_B)\right) ≤ 2 ε ( cost ( P R ) + cost ( P B ) ) ≤ 2 ε cost ( P ) . \le2\varepsilon\operatorname{cost}(\mathcal{P}). ≤ 2 ε cost ( P ) . Composition
Movement coresets may be applied repeatedly: a coreset of a coreset is also a coreset of the original input, under the composed movement rule. The errors accumulate additively, as the next lemma makes precise.
Lemma 5.9 (Composition of movement coresets). Let ( S , w ) (S,w) ( S , w ) be an ε 1 \varepsilon_1 ε 1 movement coreset of X X X with movement rule π 1 : X → S \pi_1:X\to S π 1 : X → S Let ( T , u ) (T,u) ( T , u ) be an ε 2 \varepsilon_2 ε 2 movement coreset of the weighted instance ( S , w ) (S,w) ( S , w ) interpreted as a multiset, with movement rule π 2 : S → T \pi_2:S\to T π 2 : S → T and weights
u ( t ) = ∑ s : π 2 ( s ) = t w ( s ) . u(t)=\sum_{s:\pi_2(s)=t}w(s). u ( t ) = s : π 2 ( s ) = t ∑ w ( s ) . Then ( T , u ) (T,u) ( T , u ) is an ( ε 1 + ε 2 + ε 1 ε 2 ) (\varepsilon_1+\varepsilon_2+\varepsilon_1\varepsilon_2) ( ε 1 + ε 2 + ε 1 ε 2 ) movement coreset of X X X under the composed movement rule π 2 ∘ π 1 : X → T \pi_2\circ\pi_1:X\to T π 2 ∘ π 1 : X → T
Proof. The weights are consistent with the composed rule because
u ( t ) = ∑ s : π 2 ( s ) = t w ( s ) = ∣ ( π 2 ∘ π 1 ) − 1 ( t ) ∣ . u(t)=\sum_{s:\pi_2(s)=t}w(s)=\left|(\pi_2\circ\pi_1)^{-1}(t)\right|. u ( t ) = s : π 2 ( s ) = t ∑ w ( s ) = ( π 2 ∘ π 1 ) − 1 ( t ) . Fix a k k k P \mathcal{P} P X X X Q = π 1 ( P ) \mathcal{Q}=\pi_1(\mathcal{P}) Q = π 1 ( P ) ( S , w ) (S,w) ( S , w )
cost S , w ( Q ) ∈ ( 1 ± ε 1 ) cost ( P ) . \operatorname{cost}_{S,w}(\mathcal{Q})\in(1\pm\varepsilon_1)\operatorname{cost}(\mathcal{P}). cost S , w ( Q ) ∈ ( 1 ± ε 1 ) cost ( P ) . Since Q \mathcal{Q} Q
cost T , u ( π 2 ( Q ) ) ∈ ( 1 ± ε 2 ) cost S , w ( Q ) . \operatorname{cost}_{T,u}(\pi_2(\mathcal{Q}))\in(1\pm\varepsilon_2)\operatorname{cost}_{S,w}(\mathcal{Q}). cost T , u ( π 2 ( Q )) ∈ ( 1 ± ε 2 ) cost S , w ( Q ) . Since π 2 ( Q ) = ( π 2 ∘ π 1 ) ( P ) \pi_2(\mathcal{Q})=(\pi_2\circ\pi_1)(\mathcal{P}) π 2 ( Q ) = ( π 2 ∘ π 1 ) ( P )
( 1 + ε 2 ) ( 1 + ε 1 ) cost ( P ) = ( 1 + ε 1 + ε 2 + ε 1 ε 2 ) cost ( P ) , (1+\varepsilon_2)(1+\varepsilon_1)\operatorname{cost}(\mathcal{P})=(1+\varepsilon_1+\varepsilon_2+\varepsilon_1\varepsilon_2)\operatorname{cost}(\mathcal{P}), ( 1 + ε 2 ) ( 1 + ε 1 ) cost ( P ) = ( 1 + ε 1 + ε 2 + ε 1 ε 2 ) cost ( P ) , and the lower bound is at least
( 1 − ε 2 ) ( 1 − ε 1 ) cost ( P ) ≥ ( 1 − ε 1 − ε 2 ) cost ( P ) . (1-\varepsilon_2)(1-\varepsilon_1)\operatorname{cost}(\mathcal{P})\ge(1-\varepsilon_1-\varepsilon_2)\operatorname{cost}(\mathcal{P}). ( 1 − ε 2 ) ( 1 − ε 1 ) cost ( P ) ≥ ( 1 − ε 1 − ε 2 ) cost ( P ) . This is stronger than the claimed symmetric error.
The following lemma gives the corresponding composition result for bounded-movement coresets.
Lemma 5.10 (Composition of bounded-movement coresets). Let ( S , w ) (S,w) ( S , w ) ε 1 \varepsilon_1 ε 1 δ 1 \delta_1 δ 1 X X X π 1 : X → S \pi_1:X\to S π 1 : X → S ( T , u ) (T,u) ( T , u ) δ 2 \delta_2 δ 2 ( S , w ) (S,w) ( S , w ) π 2 : S → T \pi_2:S\to T π 2 : S → T
u ( t ) = ∑ s : π 2 ( s ) = t w ( s ) . u(t)=\sum_{s:\pi_2(s)=t}w(s). u ( t ) = s : π 2 ( s ) = t ∑ w ( s ) . Then ( T , u ) (T,u) ( T , u ) ( δ 1 + ( 1 + ε 1 ) δ 2 ) (\delta_1+(1+\varepsilon_1)\delta_2) ( δ 1 + ( 1 + ε 1 ) δ 2 ) X X X π 2 ∘ π 1 : X → T \pi_2\circ\pi_1:X\to T π 2 ∘ π 1 : X → T
Proof. Fix a k k k P \mathcal{P} P X X X Q = π 1 ( P ) \mathcal{Q}=\pi_1(\mathcal{P}) Q = π 1 ( P ) ( S , w ) (S,w) ( S , w )
dist ( x , π 2 ( π 1 ( x ) ) ) ≤ dist ( x , π 1 ( x ) ) + dist ( π 1 ( x ) , π 2 ( π 1 ( x ) ) ) . \operatorname{dist}(x,\pi_2(\pi_1(x)))\leq\operatorname{dist}(x,\pi_1(x))+\operatorname{dist}(\pi_1(x),\pi_2(\pi_1(x))). dist ( x , π 2 ( π 1 ( x ))) ≤ dist ( x , π 1 ( x )) + dist ( π 1 ( x ) , π 2 ( π 1 ( x ))) . The first term is bounded by the assumed bound in (37) for π 1 \pi_1 π 1 Q \mathcal{Q} Q P \mathcal{P} P π 2 \pi_2 π 2
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( π 1 ( x ) , π 2 ( π 1 ( x ) ) ) ≤ δ 2 cost S , w ( Q ) ≤ δ 2 ( 1 + ε 1 ) cost ( P ) . \sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(\pi_1(x),\pi_2(\pi_1(x)))\leq\delta_2\operatorname{cost}_{S,w}(\mathcal{Q})\leq\delta_2(1+\varepsilon_1)\operatorname{cost}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( π 1 ( x ) , π 2 ( π 1 ( x ))) ≤ δ 2 cost S , w ( Q ) ≤ δ 2 ( 1 + ε 1 ) cost ( P ) . Combining the two bounds proves the claim.
Movement Costs and Nearest-Neighbor Reweighting
The constructions above sometimes analyze a convenient intermediate movement rule before reweighting according to nearest neighbors. Since this reweighting can only decrease the movement distance of each input point, the bounded-movement guarantee is preserved, as formalized by the next lemma.
Lemma 5.11 (Nearest-neighbor reweighting). Let S ⊆ X S\subseteq X S ⊆ X ( S , w 1 ) (S,w_1) ( S , w 1 ) ε \varepsilon ε π 1 : X → S \pi_1:X\to S π 1 : X → S π 2 : X → S \pi_2:X\to S π 2 : X → S w 2 w_2 w 2 ( S , w 2 ) (S,w_2) ( S , w 2 ) ε \varepsilon ε π 2 \pi_2 π 2
Proof. For every x ∈ X x\in X x ∈ X
dist ( x , π 2 ( x ) ) ≤ dist ( x , π 1 ( x ) ) . \operatorname{dist}(x,\pi_2(x))\leq\operatorname{dist}(x,\pi_1(x)). dist ( x , π 2 ( x )) ≤ dist ( x , π 1 ( x )) . Therefore, for every k k k P \mathcal{P} P X X X
∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π 2 ( x ) ) ≤ ∑ A ∈ P ∣ A ∣ ∑ x ∈ A dist ( x , π 1 ( x ) ) ≤ ε cost ( P ) . \sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(x,\pi_2(x))\leq\sum_{A\in\mathcal{P}}|A|\sum_{x\in A}\operatorname{dist}(x,\pi_1(x))\leq\varepsilon\operatorname{cost}(\mathcal{P}). A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π 2 ( x )) ≤ A ∈ P ∑ ∣ A ∣ x ∈ A ∑ dist ( x , π 1 ( x )) ≤ ε cost ( P ) . Since the new weights are defined according to π 2 \pi_2 π 2 ε \varepsilon ε
AI Disclosure
The authors used ChatGPT (OpenAI) as a writing and research-development aid, both to improve the clarity of author-written text and to write up proof details from author-provided ideas, proof sketches, and mathematical guidance. All results, definitions, and proof strategies originate with the authors, who verified all AI-assisted content and are fully responsible for the integrity, accuracy, and originality of the entire paper.
