Our bicriterion algorithm is an adjustment to the algorithms of [1]} and [CCF] with the following important difference: our bicriterion is online, so we do not delete and reassign centers as is [1]}. This “online" property is critical for the algorithm to work and is one of the main technical ideas. Although a fully online bicriterion can require linear space, we maintain a division of the stream \(P\)  into a prefix \(R\)  and a suffix \(P \setminus R\)  such that our bicriterion is online on the suffix \(P\setminus R\)  and the prefix \(R\)  can be largely ignored. To maintain this property of being online for the suffix, we incur only a modest space increase from \(O(k \log n)\)  to \(O(\log ( \frac{1}{\epsilon } ) k \log n)\) .
