Reviews: Fast and Provably Good Seedings for k-Means

Technical quality: I have two doubts regarding the proof of their Lemma 2: 1. The authors argue, in the case of \phi_{C}(X) \epsilon_1\phi_{c_1}, the claim holds trivially. I don't see how this goes through. First, I don't see why A {c_1}(C,l) \phi_{C}(X). As I understand it, A {c_1}(C,l) is the expected cost of C while \phi_{C}(X) is the actual cost of C (random quantity).