First, let us describe how the algorithm of [1]} works. We will modify this algorithm as part of our coreset construction. In this summary, we alter the presentation from that of [1]} to more fluidly transition to our modified version but the algorithm remains the same. [1]} operates in phases \(i \ge 1\) . This means that the algorithm maintains a phase number \(i\)  (used internally by the algorithm), beginning in phase \(i=1\) . As the stream arrives, the algorithm may decide to increment the phase number. Let \((R_i,w_i)\)  denote the prefix of the input received before the end of phase \(i\) , and let \(\text{\footnotesize \textsf {OPT}}_k(R_i)\)  denote the minimal value of \(\bar{g}(R_i,w_i,C)\)  over every \(C \in Q\) .
When phase \(i+1\)  begins, a value \(L_{i+1}\)  is declared on Line REF  as a lower-bound for the current value of \(\text{\footnotesize \textsf {OPT}}_k(R_{i+1})\) . The algorithm has computed \((M_i, u_i)\) , which we inductively assume is a bicriterion approximation for \(R_i\)  (more precisely, a map \(\mathcal {B} : R_i \rightarrow M_i\)  such that \(\cup _{p \in R_i} (\mathcal {B}(p), w(p)) = (M_i,u_i)\) . However, to maintain polylogarithmic-space the algorithm pushes \((M_i, u_i)\)  to the beginning of the stream and restarts the bicriterion construction. This means that the algorithm, at this point, restarts by viewing the stream as \((P, w - w_i + u_i)\)  (i.e. replacing \((R_i,w_i)\)  with \((M_i,u_i)\) ). Continuing in this way, the algorithm maintains a bicriterion \((M_{i+1},u_{i+1})\)  for \((R_{i+1},w_{i+1} - w_i + u_i)\)  (which is also a bicriterion for \((R_{i+1},w_{i+1})\)  by Theorem REF ) until the next phase change is triggered.
