www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/clustering/sohler2010.pdf
obtain
d2(qp, C) ≥ (1− 2ε+ ε2)d2(p, C) > (1− 2ε)d2(p, C) .
Hence, we get
d2(p, C)− d2(qp, C) ≤ 2εd2(p, C) < 3εd2(p, C) .
C Proof of Proposition 3.2
Since d(p, qp) > εd(p, C) and ε ≤ 1, we have∣∣d2(p, C)− [...] C)− d2(qp, C) ∣∣ ≤ 3
ε d2(p, qp) .
Using Proposition 3.1 and 3.2, we nd∣∣cost(P,C)− costw(S,C) ∣∣
≤ ∑ p∈P ′
∣∣d2(p, C)− d2(qp, C) ∣∣
+ ∑ p∈P ′′
∣∣d2(p, C)− d2(qp, C) ∣∣
≤ 3ε ∑ p∈P ′
d2(p, C) + 3 ε
∑ p∈P ′′ [...] 8(2+lnm) ,
we have with high probability
cost(P, S) ≤ 8 δ
(2 + lnm)optm(P )
≤ ε2optk(P ) ≤ ε2cost(P,C)
for m = Θ ( k logn δd/2εd logd/2
( k logn δd/2εd
)) . Therefore, the
theorem follows.
4 The Coreset …
