  We study k-median clustering under the sequential no-substitution setting. In
this setting, a data stream is sequentially observed, and some of the points
are selected by the algorithm as cluster centers. However, a point can be
selected as a center only immediately after it is observed, before observing
the next point. In addition, a selected center cannot be substituted later. We
give the first algorithm for this setting that obtains a constant approximation
factor on the optimal risk under a random arrival order, an exponential
improvement over previous work. This is also the first constant approximation
guarantee that holds without any structural assumptions on the input data.
Moreover, the number of selected centers is only quasi-linear in k. Our
algorithm and analysis are based on a careful risk estimation that avoids
outliers, a new concept of a linear bin division, and a multiscale approach to
center selection.
