I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is a $(k, ε)$-coreset for $P1 ∪ P2$. (ii) If $C1$ is $(k, ε)$-coreset for $C2$, and $C2$ is a$(k, δ)$-coreset for $C3$, then $C1$ is a $(k, ε+δ)$- coreset for $C3$
Can anyone please figure it out?
The k-medians clustering objective is defined here as
sum_{p in points} weight(p) distance(p, centers)
where centers is the set of k centers and distance(p, centers) is the distance to the closest center.
The first observation amounts to observing that the objective function is additive. Letting (C1, w1) and (C2, w2) be the core-sets, we consider the core-set (C1 union C2, w1 union w2), which satisfies
sum_{p in C1 union C2} (w1 union w2)(p) distance(p, centers)
= sum_{p in C1} w1(p) distance(p, centers) + sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) sum_{p in P1} weight(p) distance(p, centers) + exp(eps) sum_{p in P2} weight(p) distance(p, centers)
= exp(eps) (sum_{p in P1 union P2} weight(p) distance(p, centers))
and similarly for the lower bound.
As for the second observation,
sum_{p in C1} w1(p) distance(p, centers)
<= exp(eps) sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) exp(delta) sum_{p in C3} w3(p) distance(p, centers)
= exp(eps + delta) sum_{p in C3} w3(p) distance(p, centers),
and similarly for the lower bound.
Proof of claim 1:
For every query q of k points we have:
$Cost(C1\bigcup C2,q)=Cost(C1,q)+Cost(C2,q)\\ \leq (1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$
And a similar proof can be made for the lower bound.
Claim 2 is only approximately correct for small values of $\epsilon,\delta$.
Proof of claim 2:
$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$
And a similar proof can be made for the lower bound.
