A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering
Authors: Tom Hess
Michal Moshkovitz
Sivan Sabato
Venue: NeurIPS 2021 Poster (2021)
Keywords: k-median clustering
constant approximation
sequential algorithms

Abstract: 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 cost 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 cost estimation that avoids outliers, a new concept of a linear bin division, and a multi-scale approach to center selection. 

A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k--Median Clustering
Tom Hess
Michal Moshkovitz
Department of Computer Science Ben-Gurion University of the Negev
Department of Computer Science
Tel-Aviv University"
Beer-Sheva, Israel tomhe@post. bgu.ac.
Tel Aviv, Israel mmoshkovitz@eng ucsd. edu
Sivan Sabato
Department of Computer Science Ben-Gune Ben-Gurion University of the Negev Beer-Sheva, Israel sabatos@cs, bgu. ac.
Abstract
We study k-median clustering under the sequential no-substitution setting. In this setting, data stream is sequentially observed, and some of the points 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 constant approximation factor on the optimal cost under random arrival order, an exponential improvement over previous work. This 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 Our algorithm and analysis are based on careful cost estimation that avoids outliers, new concept of a linear bin division, and multiscale approach to center selection.
Introduction
Clustering is a fundamental unsupervised learning task used for various applications, such as anomaly
2008 and cancer diagnosis [Zheng el al. [014]. In recent years, the problem of sequential clustering has been actively studied, motivated by applications in which data arrives sequentially, such online recommender
detection [Leung and Leckie, 2005), recommender systems (Shepitsen
systems (Nasraoui et al. 2007] and online community detection Aggarwal 2003
In this work, study k-median clustering in the sequential no-substitution setting, term first introduced in Hess and Sabato 2220)]. In this setting, a stream of data points is sequentially observed, and some of these points selected by the algorithm be selected as center only immediately after it is observed, before observing the next point. In addition, selected center cannot be substituted later. This setting is motivated by applications in which center selection is mapped to a real-world irreversible action. For instance, consider a stream of website users, where the goal and provide them with a promotional gift while they are still on the website. As another example, consider recruiting representative participants for clinical trial out of stream of incoming patients.
cluster centers. However, point can
instantaneously identify users that serve as social cluster centers
This work done while the author the University of California San Diego
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The goal in the no no-substitution k-median setting is to obtain a near-optimal k-median cost value, while selecting a number of centers that is close as possible to For an adversarially ordered stream, it has been shown [Moshkoviz] [02T] that an algorithm that selects a number of centers that is sublinear in the stream length cannot obtain constant approximation guarantee, unless some structural assumptions are imposed on the input data.
In this work, we show that in contrast, when the stream order is random, a constant approximation guarantee can be obtained without imposing structural assumptions on the data. Previous works on the random-ordes setting provide either an algorithm with an dlmost-constan approximation assuming a bounded metric space [Hess and Sabato 2020] or an algorithm with an approximation factor that is exponential in & [Moshkovitz, 2021]. Thus, our guarantees are stronger and more general than the previous guarantees. Moreover, the number of centers selected by our algorithm is only quasi-linear in & and does not depend on the stream length.
Main result. We propose a new algorithm, MUNSC (Multiscale No-Substitution Clustering), that obtains constant approximation factor with probability ô over the random order of the stream, while selecting only O(k log" (k) centers. MUNSC operates by executing several instances of new center-selection procedure, called SelectProc, where each instance is applied to a stream prefix of a different scale. SelectProc decides which centers to select using novel technique, in which small stream prefix is used to estimate truncated version of the optimal cost of the entire stream. This truncated version ignores outliers, and so can be estimated reliably. The value of the estimate is used to determine which centers to select from the rest of the stream. The multiscale use of SelectProc by MUNSC allows MUNSC select only a quasi-linear number of centers.
As part of our analysis, we propose a new concept of a linear bin division, which allows a high- probability association of the costs of stream subsets, while selecting number of centers that is independent of the stream length. This improves previous construction of Meyerson et al. [2004)
The guarantees for MUNSC are provided in our main theorem, Theorem 4.1 stated in Section 4 Table T
below compares our guarantees to previous works; See Section 2 for additional details. We note that our algorithm and guarantees are easily extendable to k-means clustering, other clustering objective that satisfies the weak triangle inequality. MUNSC uses as a black box an offline k-median approximation algorithm with constant approximation factor. Whenever the offline algorithm is efficient [e.g.. Charikar et al. 2002 Li and Svensson 2016), then so is MUNSC.
well as any
Limitations. The proposed algorithm is the first constant-aprroximatin no-substitution clustering algorithm that makes no structural assumptions on the input data set. The only limitation is the assumption that the input order is random. This assumption is useful in cases where there is no adversary and any order is as likely, as in the example applications mentioned above. Moreover, a random order is standard assumption in many streaming settings, satisfied also whenever the input stream is drawn i.i.d. from a distribution. In some cases, the randomness assumption might hold only approximately. In these cases, we expect graceful degradation of the guarantees. We leave for future work a comprehensive treatment of input orders that are neither random nor adversarial. We expect the techniques of the current work to serve cornerstone in such treatment.
Paper structure. We discuss related work in Section 2 The formal setting and notations are defined in S The algorithm and its guarantees are given in Section [ In Section[5] we outline the proof of the main result. Some parts the proof are deferred to appendices, which can be found in the supplementary material. We conclude with discussion in Section
2 Related Work
Several works have studied settings related the no-substitution k-median clustering setting. Table [ summarizes the upper bounds mentioned below. First, some works studied related settings under an adversarial arrival order. Liberty al. (2016) studied online k-means clustering, in which centers are sequentially selected, and each observed point is allocated to one of the previously selected centers. The proposed algorithm can be applied to the no-substitution setting, yielding an approximation factor of (log()))) where is the stream length. For this algorithm to select sublinear number of centers, the aspect ratio of the input data must be bounded. Bhhakkara and Rwanpathirana (2020) studied the same setting as Liberty et al. 20166) improving the approximation factor to constant, under

---

Table 1; Comparing our guarantees to previous works. is the stream length. Abbreviations: LSS Liberty et al. 2016], BR20: Bhaskara and Rwanpathirana 2020 BM20: Bhattacharjee and
Moshkovitz 2021] Mo21: Moshkovitz [021]. HS20: Hess and Sabato 2020].
Reference
arrival order
assumptions
approximation factor
number of centers
LSS16
adversarial
bounded aspect ratio O(log(n))
O(klog
BR20
adversarial
bounded aspect ratio
constant
O(klog"(n) (n))
BM20
adversarial
data properties
O(k*)
O(k log(k) (k) log(n))
Mo21
random
exponential in k
O(k2) or Ol log(n))
HS20
random
bounded diameter
addstie
This work
random
none
constant
O log (k))
the same assumptions. BBhataccarree and Moshkovitz [2021 explicitly studied the no-substitution setting, and provided an approximation factor of O(k)) under different assumption on the input data set.
The setting of random arrival order has been studied in several recent works. Hess and Sabato 22200) proposed an algorithm that selects exactly &t centers. They obtained a constant approximation factor, with an additional additive term that vanishes for large streams, under the assumption that the metric space has bounded diameter. Their guarantee with high probability. Moshkovitz [202T) obtained an approximation factor that is exponential in k, with a number of centers that is linear in and logarithmic in the stream length n. Assuming a known stream length, the same work also obtained an approximation factor which is exponential in & while selecting (k-5) centers. Both guarantees hold only with a constant probability. As can be seen in Table T to date, the only known constant opproximation algorithms for no-substitution k-median clustering impose structural assumptions on the input data.
A related sequential clustering setting is the streaming setting (c.g.. Guha et al. 2000 Ailon et al. 2009, Chen 2009 Ackermann et al. 2012 Braverman al. 2016), which the main restriction is the amount of memory available to the algorithm. This setting allows substituting selected centers, but algorithms in this setting can be used the no-substitution setting, by collecting all the centers ever selected. However, we are not aware of any algorithm in this setting with a competitive bound on the total number of selected centers.
Setting and Notation
For an integer i, denote [i] == f1.... (1....,,) i). Let (X, be finite metric space. where X is a set of size n and p X X + R is a metric. For a point E X and a set C X, we denote p(æ,, T) == min p(x, y). For an integer k > 2, k-clustering of X is set of (at most) k points from X which represent cluster centers. Throughout this work, whenever an item is selected based on minimizing p. we assume that ties are broken based on a fixed arbitrary ordering. Given a set S SC X, the k-median cost of T on is cost(S, 7') := Eres p(x, T). The k-median clustering problem aims to select a k-clustering T of X with a minimal overall cost cost cost(X, TT, We denote by OPT an optimal solution to this problem: OPT E argminrcx,iTjs cost(X, X, T). In the sequential no-substitution k-median setting that we study, X is not known a priori. The points from X are presented to the algorithm sequentially, in a random order. We assume that the stream length, n, is provided as input to the algorithm; see Section 6 for a discussion on supporting an unknown stream length. The algorithm may select an observed point as a center only before observing the next point. Any selected point cannot later be removed or substituted. The goal of the algorithm is to select small number of centers, such that with high probability, the overall cost of the selected set on the entire X approximates the optimal k-median cost, cost(X, OPT). In other words, we seek an algorithm with a low competitive ratio, in the sense of competitive analysis [Borodin and El- Yaniv 2005). An offline k-median algorithm A is algorithm that takes input finite set

---

Algorithm The sequential clustering algorithm: MUNSC
input E (0, 1), N, n N (stream length), A (an offline k-median algorithm), sequential access to the input stream.
01 f (4k); For i N. a, <- 01 2
2: I + [log2 (1/(0/1)))))))
) 8 + 6/) A is set so that a1+1 E (1/12, copies of SelectProc. indexed by i [I + 1], as follows:
3: Prepare
In all copies, use inputs k, A. < 0art1 and set the confidence parameter to 8'.
copy E [T + 1]. set a < 04;-
In all but the last copy, set M <- and
20,,-
the last copy (index + 1), set M t- log(8k+ (o/(///+'))) and 7. + + - -
4: Read each point from the input stream and feed it to each of the copies of SelectProc. If any of the copies selected the point, then select it as a center.
of points S and the parameter k, and outputs k-clustering of S, denoted A(S, k). For 8 > say that A is 3-approximation offline k-median algorithm on (X, if for all input sets S X, cost(S, A(S, k)) 3 cost(S, OPTs), where OPTs is optimal solution with centers from S. Formally, OPTs E argminggs./risa cost(S,7)
The algorithm
In this section, we describe the proposed algorithm, MUNSC. MUNSC receives as input the value of k, the confidence level (0, and the total stream length n. We further assume access to some black-box offline k-median algorithm A. The guarantees of MUNSC depend on the approximation factor guaranteed by A. MUNSC has only sequential access the input stream. Our main result is the following theorem, showing that MUNSC obtains a constant approximation factor with a quasi-linear number of centers. proof sketch of the theorem given in Section 5 The full proof is provided in the supplementary.
Theorem 4.1. Let k, n E N. L E (0, 1). Let (X, p) be a metric space of size n. Let Tont be the set of centers selected by MUNSC for the input purameters 8, k, n. Suppose that the input stream is random permutation of X, and that the input black-box algorithm A is 3-approximation offline k-median algorithm. Then, with a probability at least
1. [Touel O(k (ogklog2(//// and
2. cost(X, Tont) S C3 cost (X, OPT), where C > 0 is universal constant.
We first give, in Section 4.1 short overview of the structure of MUNSC. A core element of the algorithm is the internal procedure SelectProc, which is used by MUNSC with several different sets of input parameters, creating a multiscale effect that we discuss below. We explain the details of SelectProc in Section 4.2 Then, in Section 4.3 we explain the design of MUNSC.
4.1 Algorithm structure overview
MUNSC is listed in Alg. 1 works as follows: It initializes O(log(k/)) copies of the procedure SelectProc, each with a different set of input parameters, where we define d., := 150 log(32k) (32k/8) /8)/a for a > then iteratively reads the points from the input stream one by one, and feeds each point to each of the copies of SelectProc, that each copy sequentially observes the entire input stream. Whenever any copy of SelectProc selects point as a center, this point is selected by MUNSC as a center.
The internal procedure SelectProc uses a robust cost estimation approach to select a small number of centers. The procedure gets as input several technical parameters, in addition to the input parameters of MUNSC. We explain the procedure and the meaning of the technical parameters Section 4.2 The values of the technical parameters set by MUNSC for each of the copies of SelectProc ensure that MUNSC select a small number of centers, while obtaining constant approximation factor. This done using multiscale approach. We discuss this in detail in Section 4.3

---

Algorithm 2 Internal procedure: SelectProc
input 8 E (0, 1), N, n N, A (an offline k-median algorithm), sequential access to the input stream.
Technical parameters: a E (0. T ( 2a), M E N
1: A Phase I (Calculate an initial clustering Ta):
2: Pi <- the first on points from the input stream.
3: To == {cI,... Ck,, f A(Pi, ( k4) A Only calculation, centers are actually selected here. a on large optimal clusters):
4: A Phase 2 (Estimate the cost a
5: P2 < next on points from the input stream.
6: di + 3a costaa(k+11) (P2, Ta.) A vp estimates the cost T
Ta on large optimal clusters.
7: A Phase 3 (Select centers):
8: E [k+4], n; + 0, Near, + FALSE.
A Th counts selected points associated with c;. Near, indicates if a point close to c₁ selected.
9: for yn iterations do
10: Read the next point x from the input stream.
11:
<- argmin,g[k,, p(z, G.) Find the closet center to x in Tax-
if p(z, q.) > d or -Near, or n4 M then
13:
Select x as a center. A This is the only line in which actual selections occur.
n4 4- n, +
1 15: If p(ar, (4) ke
then Near, < TRUE.
end if
17: end for
4.2 The internal procedure: SelectProc
In this section, we present the internal procedure, SelectProc. has been observed previous work [Liberty et al.) [016] that knowing in advance the optimal cost on the entire stream allows a successful center selection. Under a random arrival order, one may hope that obtaining a good estimate for the optimal cost would be straight-forward However, since the metric space is unbounded, even small number outliers can bias the cost estimate considerably. We overcome this challenge by showing that it suffices estimate version of the optimal cost that ignores outliers, and that this version be estimated reliably from a small prefix the stream. Our analysis is based on a distinction between small and large optimal clusters, which formally define in Section below.
SelectProc, listed Alg. 2. uses the following notation. For two sets S,T C X and an integer denote by far, (S, T) C 5 the set of points in S that are the furthest from T according to the metric p. If [S] < r, we define far, (S, == S and call (S,, a trivial far set. Denote by (S, cost S \ far, (S, T), T) the cost of T S after discounting the points that incur the most cost. Let k == + 38 log (32k/ 32k/ SelectProc receives the same input parameters as MUNSC. In addition, it requires several technical parameters, denoted a, 7, A and r. We explain the meaning of these parameters in the proper context below.
SelectProc works in three phases. For E [3]. we denote by P; the set of points that are read in phase In each the first two phases, an a fraction of the points the stream is read. In the last phase, y fraction of the points in the stream is read. Note that depending y, the procedure may ignore suffix of the stream. The first two phases are used for calculations. Centers are selected only during the third phase.
the values of a and
In the first phase, reference clustering Ta calculated using the input offline algorithm A. Note that the centers in T. cannot be selected as centers by SelectProc, since A calculates T. only after observing all the points the phase. the second phase, an estimate v the cost of of, ", calculated. In the third phase, SelectProc observes points from the stream one by one, deciding for each one whether should be selected
center. For each observed point, SelectProc first finds the center E Ta which is closest to it. A point is then selected as a center if it satisfies one of three conditions: (1) its distance from 6 is more than (/(k)) (where is one of the input technical parameters); (2) e; does not yet have M associated points (where M is one of the technical parameters); or (3) point close to e; been selected so far, as maintained by the Boolean variable Near,. Theorem 5. in Section we provide guarantee on the output of SelectProc, which upper bounds the number of
5

---

centers selected by SelectProc and the cost obtained by these centers, as a function of the technical parameters.
Challenges and solutions in SelectProc. We give here an informal explanation of the workings of SelectProc. The full analysis is provided in Section and the supplementary. Consider the clusters induced by some fixed optimal k-median clustering on X. Call these clusters optimal clusters. Optimal clusters that are large (that is, include a sufficiently large fraction of X) are easy identify from a small random subset of points. Therefore, approximate centers for these clusters will be identified in the first phase of SelectProc by the black box algorithm A. and will be included in Ta. Thus, the cost of Ta on the subset of points that belong to large optimal clusters will be close to optimal. Note that Ta is a clustering with k+ > centers. This overcomes the fact that the data set might include outliers which are not proportionally represented in each phase. Searching for a k-clustering in P1 might thus lead to a clustering that is too biased towards such outliers. By increasing the size of the solution searched in the first phase to k4, this allows the solution to include the outliers as centers, while still choosing also centers that are close to the optimal centers of all large clusters. The selection conditions of the third phase further guarantee that at least M points are selected near each center e; E T, which represents a large cluster, thus making sure that a center which is very close to each such c; is selected. This allows bounding the obtained cost on points in large optimal clusters.
An additional challenge is to ensure that points in small optimal clusters are not too far from the set Tout of all selected centers. Since the metric space is unbounded, even a single such point can destroy the constant approximation factor. To overcome this, SelectProc selects point near each center in Ta, as well as all the points that are far from Ta. The threshold e v/(kT), which defines a point as far, is set so that the number of points selected from large optimal clusters can be bounded. This bound crucially relies on the accuracy of vi as an estimate for the cost of Ta on large clusters. The required accuracy is obtained by ignoring the points that are furthest from Ta when calculating the cost on P2 (see line (). For small clusters, they hold a small number of points by definition, thus the number of such points selected as centers is also bounded.
4.3 The clustering algorithm: MUNSC
As described above, MUNSC runs several copies of SelectProc the same input stream: each point is read from the input stream and then fed to each of the copies of SelectProc. Each of these copies selects some centers, and the set of all selected centers is the solution of MUNSC. The difference between the copies is in the value of the technical input parameters. First, the value of a (the stream fraction for the first and second phases) is progressively doubled, starting with on = 5/(4k) and ending with 07+11 = 01 2", where 1 is set so that 07+1 E (1/12, 1/6]. The value of 7 (which controls the selection threshold) set to dar in all copies, based on the largest value of a. In all but the last copy, Y (the stream fraction for the third phase) is set to 20,, where i is the copy index. This means that the first and second phase of copy are each of size at, while the third phase is of size 20; (the rest of the stream is ignored by copy i). Therefore, copy i observes a 4a; 2a fraction of the stream. Thus, the first two phases of copy i i+ 1 exactly overlap with the fraction of the stream observed by copy i. Figure Tillustrates the overlap of phases in consecutive copies of SelectProc. In the last copy, indexed by T 1, 7 is set 1 20 thus this copy reads the entire stream. It can be seen that each point, except for the first 2n points, participates in the third phase of exactly one copy of SelectProc. As our analysis below shows, this overlap between the phases guarantees that the set of centers selected by the copies of SelectProc obtains a small cost on all the small optimal clusters. The last copy is slightly different: in addition to setting the length of the third phase y to include all the points of the stream, it also sets the technical parameter M to a number larger than We show below that in this way, the selected set of centers obtains a small cost on large optimal clusters well.
The use of several copies of SelectProc with different phase sizes ensures that MUNSC selects only a quasi-linear number of centers, by overcoming the following challenge: On the one hand, the first phase and the second phase must small, otherwise we might miss point that needs to selected, since no points are selected in these two phases. On the other hand, small first and second phases lead to poor quality of the reference clustering T., The multiscale approach makes sure that almost all points participate in some selection phase, while at the same time improving the quality of T, as

---

d P2
Bay (selection))
1st copy
20g
2n
4n Pa (selection)
2nd copy
P2
401
80y
3ed copy
P5 (snlection)
Figure Illustrating the phases in copies 1, 2,3 of SelectProc within MUNSC.
grows. Our analysis below shows that in this way, the number of centers selected by each copy remains similar, even though larger values of a lead to a larger selection phase.
Using MUNSC in a bounded memory setting. MUNSC can be used a bounded memory setting, by using 1-pass streaming clustering algorithm as the black-box algorithm A. For instance, the algorithm Charikar et al. 2003) requires O polylog(n)) memory. MUNSC can be implemented to require additional memory of only O log(k/6) on top of the requirements of the black- box algorithm. We now explain in full how this can be done. First, consider the memory requirements of SelectProc: In phase the points
be fed to A one by one and do not need be saved in memory. Only To. the k = O(k + log(3 ( )) output points of A, need to be saved in memory. In phase 2, calculating the truncated cost of Ta on P2 can be done by saving at most 2x (k- (k+1)), O(k log( ))) at any time, so as to identify the farthest points from To, which are the ones to disregard. In phase the points are inspected one by one and do not need to be saved in memory (if one wishes to save the selected centers in memory, although this is not in principle required in our setting, then an additional Ok log( )) factor is added). In total, SelectProc can be implemented using a memory size of Okk log( )) )) + the memory requirments of AA MUNSC runs (())g())) parallel runs of SelectProc. Thus, it requires at most memory size of Olog(( &
8 (k log( + the memory requirements of A)). In fact, this can be made even more memory-efite eeffory-fffiieet, by using an algorithm A which is streaming anytime algorithm. In this case, it is possible to use single copy of A for all the parallel runs of SelectProc, since P in the i'th copy of SelectProc is the prefix of P1 the + I'th copy (see Figure D). That is, A is run on the entire stream and whenever phase 1 of any copy ends, its current set of centers is retrieved for this copy. In this case, the memory size required by MUNSC is (l log" ( (t)) + the memory requirements of A.
5
Analysis
In this section, we give an overview of the proof of Theorem proof. Denote the centers the optimal solution OPT by (c tec. and the clusters induced by OPT (the optimal clusters) by {C; hek. Formally, C; := fi E X 2 == argminje P(cz. r)}. Optimal clusters with fewer than &a points are a-small optimal clusters, and the complement are a-large. Denote the indices of a-small and a-large clusters by [ = {i E [k] |C$1 Φa} and f [K] \ Iemall and the points in these clusters by Camall := UVE C and Oarre := U C To prove Theorem 4.1 we provide the following guarantee on the centers selected by SelectProc.
4.1 The supplementary provides the full
Theorem 5.1. Let k, n E N. Let 8 E (0, 1). Let (X, .) be metric space of size n. Let Tout be the set of centers selected by SelectProc for the input parameters 6, k. n, a E (0, 1/6,, 7 E (a, 2a)). M N, 7 > O. Suppose that the input stream is a random permulation of X, and that A is 3-approximation offline k-median algorithm. Then, with a probability at least - 6/2,
1. Tourl = - = (og((()))))) + kr + +(k + (oo+k((k/))))
2. For any E [k], of Ps, then
C
;os Tomi) S cost(C), (c+) +
(36,3 + 20) OPT);
(1)
kr
3. 7 = 1 20, = da and M = loog/l//////// (8), then
cost(Ciange: Tout) cost(Olarge OPT) + (468.3 + 260))ost(X, cooos((XXOP)) OPT).
(2)
7

---

The proof of Theorem 4.1
provided in Appendix A uses part 1 to bound the total number of centers, and parts and to bound the cost of small and large optimal clusters, respectively. The statement of Theorem 5.1 hints to the reason for the multiscale design of MUNSC: On the one hand, part gives an approximation upper bound only if the cluster center appears the third phase. For this hold with high probability, the third phase needs to be very large. On the other hand, for quasi-linear bound on selected centers in part the ratio between the third phase and the first phases (7/a) needs to be small. The multiscale design overcomes this by keeping the ratio constant in each copy of SelectProc, while ensuring that the union of all third phases is almost the entire stream.
In the rest of the section, we give the proof of Theorem 5.1, In Section 5.1 we introduce the concept of linear bin divisions, and derive its properties. In Section [5.] we give an overview of the proof of Theorem 5.I using the results of Section 5.1 The full proof is provided in the supplementary.
5.1 Linear bin divisions
A main tool in the proof of Theorem 5.1 is partitioning sets of points from the input stream into subsets, such that each of the subsets is probably well represented in relevant random subset of the stream. Meyerson et al. [2004] defined the concept of a bin division of X with respect to clustering T. which is a partition of X into bins of equal size, where points are allocated bins based on their distance from T. Here, we define the concept of a linear bin division, in which the bins linearly increase in size. This gradual increase allows keeping the size of the first bin independent of the stream length, while still proving that with a high probability, the overlap of each of the bins in the division with random subsets of the stream is close to expected. The fixed size of the first bin is crucial for deriving guarantees that are independent of the stream length. In addition, the ratio between adjacent bin sizes kept bounded, which allows proving a bounded approximation factor.
Definition 5.2 (Linear bin division). Let W. T C X be finite sets, and 2 E N. A z-linear bin division of W with respect to T is purtition B- = (B(1), ..... BB(L) of (for an integer L) such that:
1. If S [W], then Vi E [Z] [B()] 2 2 (i+ 1)/2. Otherwise, the bin division is called trivial, and defined as B = B11 = W.
2. [B(1) S ZZ.
3. Vi E [L. - 1), |B(++ + 1)1/1B(1) 3/2.
4. Vi E [T. - 1), and Vor E B(i), x' E B(i + 1), i holds that p(x, T) 2 p(a',
A linear bin division exists for any size of W: For |W| < z, the conditions trivially hold. For [W| 2 2, the three first properties hold for the following allocation of bin sizes: Let I. be the largest integer such that B= = [ie()) 2 2(i+1)/2 - [W]. Set the size of B(i) to z (i+ 1)/2+
B)W L.
[ clearly holds. Property 2 holds since (IW) - B)/L S (=(L + 2) 2) S 3z/2. Property 3 holds since (i + + /i + + a) < 3/2 for all > 1 and any non-negative To satisfy property allocate the elements of W into the bins in descending order of their distance from T.
Property
We say that a set is well-represented in another set if the size of its overlap with the set is similar to expected. This extends naturally to bin divisions. Formally, this is defined as follows.
Definition 5.3 (Wel-trppresented). Let W be a finite set and A, B S W. We say that B is well- represented in A for W if [B n AI/|B| E [r/2, (3/2)r), where r == |AI/[W]. We say that a linear bin division of W is well represented in A for W if each bin in B is well represented in A for W.
The following lemma shows that if A is selected uniformly at random from W. then any fixed set B is well-represented in A with a high probability. Moreover, the same holds for any z-linear bin division of W with sufficiently large 2. The proof of the lemma is provided in Appendix B
Lemma 5.4. Let W be a finite set. Let B W be set, and let B be z-linear bin division of some subset W with respect to some T, for some integer z. Let A C W be a set of size r|W] selected uniformly at random from W. Then the following hold:
1. With probability at least 1 - 2e- B is well-represented in for W.
2. If 2 10 lo (T/ then with probability 1 - 6, B is well represented in A for W.
8

---

We now state and prove main property of linear bin divisions, which will allow us to use sub-streams of the input stream to bound the cost of clustering on X.
Lemma 5.5. Let W S X and let N. Let B be a z-linear bin division of W with respect to some T. Let A Ç W and r E (0, If E [L], [B() n AA/(((( S then cost(A) B(1), T) S
Proof. Let L be the number of bins in B. We first prove the following incquality, which relates the cost of the intersection of bin with A to the cost of the preceding bin.
vi E [L- - 1]. cost (at(AnBa A 1). - cost (B()). T).
(3)
To prove Eq. (3), fix i
[, 1). and denote b max p(,, T). By the assumptions,
have |A B(t ( r|i 1) Hence, cost(A Bii 1 S r|B(i 1)] b. By property
of linear bin divisions,
[B + 1) S 3 [ Therefore, cost n Bíi + +11 T) < (B()))
In addition, by property
4 of linear bin divisions and the definition of b, Vz E ( p(æ, ((x.T), T).
Therefore, (ost(B((i)
[B(i]] Combining the two inequalities, we get Eq. 3 It follows that:
3
3
cost(A) ((1,, - cost(An
Σ cost cost(B((), rcost(W,T))
This proves the statement of the lemma.
we define an event, denoted E, which holds with a high probability. We prove each of the claims in the theorem under the assumption that this event holds. To define the event, we first provide some necessary notation. Consider a run of SelectProc with some fixed set of input parameters, and assume that the input stream is random permutation of the points in X. Recall that T. (cI..... CR. is the clustcring calculated in the first phase of SelectProc, Denote the clusters induced by T. on X by Ci...., Ck., where C := {x X several sets and bin divisions, which will be used define the required event. Let B, be (0.,/1)) linear bin division of X with respect to OPT. Define F3 == farko,, (X P1, T.). and let B, be (0a/3) (3)/nerr bin division of X (PPP))) with respect to Ta- Define F. == far:(A+1)d. (X) (X)P,, and let B. be /3)/neen bin division of X (P. U F.) with respect Ta- Lastly, define Fa == fars(k+1)0.. (X) Pi, Ta.). Note that each of these objects may be trivial the stream is small.
To prove Theorem 5.1
argmin P(c,, =)). We define
Pi, Ta),
The event E is defined as the following conjunction: (1) For each i Parge C is well well-represented in P1 and in P1 U22 for X. (2) Each of F3 and F. is trivial or well-represented in P2 for X \ Pi; Fa is trivial or well-represented in P3 for X P1. (3) B, is trivial or well-represented in Pi for X: Each of B, and B, is trivial or well-represented in P2 for X \ Pt, and (4) For each E [k+]. one of the first (8k+ points observed from C₁ in P3 is closer to o than at least half of the points in C2 n Pa-
The following lemma, proved in Appendix C shows that E holds with high probability.
Lemma 5.6. Consider a run of SelectProc with fixed input parameters. Assume that the input stream is random permutation of the points of X. Then E holds with probability at least 8/2.
5.2 Theorem 5.1 proof overview
In this section, we give an overview of the proof of Theorem 5.1 The full proof given in Appendix In the first phase of SelectProc, the clustering T, is calculated using the offline algorithm A. We first bound the cost of T. points in c-large optimal clusters.
Lemma 5.7. If E holds, then cost( (ast Caagge: T.) (183 + 10)cost(X, OPT).
In the second phase of SelectProc, the goal is to estimate truncated version of the cost of T, on X. This truncated version ignores the cost on the outliers, which are the kénn furthest points from T. in X. Setting the estimate // costta((<+ 1)d., (P2, Ta) ignores the furthest 2c(k + 1)o. points in Pz. which with a high probability include all the ko outliers in X. The following lemma bounds va between two versions of truncated cost of T..
Lemma 5.8. If E holds, then ccosts (X PT,Ta) S cost (X, T.).

---

The proof Lemma 5.9 uses the lower bound be too many points that are more than (/(()) far from Ta, since this would make the truncated cost in the lower bound larger than vh. We note that the resulting upper bound is independent of the stream The proof of this lemma uses the linear bin divisions studied in Section 5.1 In particular, the upper bound uses Lemma [.3] and the lower bound uses the specific construction of the bin sizes.
From the lemmas above, it can be seen that vé is also upper bounded by the optimal cost, as follows. a-small optimal clusters smaller than Pa. thus their total size is less than kΩa- It follows that
cost
Ta)
S cost(X
Smmall+ Ta) cost(Clarge Ta).
(4)
Combining Lemma 5.7 Eq. and Lemma 5.8 we get that dp is upper bounded by the optimal cost.
In the third phase, the points selected as centers include (among others) all the points with distance of more than / (KT) from Ta. This allows bounding the cost of Tout on points in some of the optimal clusters by linear expression in /// (/rT). Combined with the upper bound on v5, this allows proving part of Theorem 5.1 Part 3 bounds the cost of Tout on large optimal clusters, for specific settings of the technical parameters SelectProc. To prove this part, we show that under these parameter settings, the centers selected based on the reference clustering Ta include sufficiently many points around each large optimal cluster. We then show that one of these points close to the optimal center.
Lastly, part of Theorem 5.1 upper bounds the number of centers selected by SelectProc. The following lemma upper-bounds the number of points that are selected because they are far from T.
Lemma 5.9. Let N [x P3 p(a, Ta) > (/+))) Under E, N S 8(k: 1) 1-a 9KT.
shown in Lemma 5.8 to conclude that there cannot
size, due to the specific construction of the bin sizes in the linear bin division. Using this lemma, we can prove part of SelectProc. The full proof of Theorem S.T given in Appendix D
Discussion
In this work. we provided MUNSC, the first constant-approxximatis algorithm for sequential no- substitution k-median clustering that does not require structural assumptions on the input data. Moreover, the number of centers selected by MUNSC is only quasi-lineat in k.
MUNSC can also be used when the stream length n is not known advance, using a simple doubling trick. Moshkovitz) [2021] showed that unknown stream length with an approximation factor that does not depend on n require a logarithmic dependence on n in the number of selected centers. Indeed, doubling trick for MUNSC would preserve the approximation factor, increasing the number of selected centers only by the unavoidable (log(n)) factor.
Funding Transparency Statement
Sivan Sabato and Tom Hess were supported in part by the Israel Science Foundation (grant No. 555/15) and by the Siieed-Stttts--aae Binational Science Foundation (BSF) (grant no. 2017641). Michal Moshkovitz has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine learning at Tel Aviv University.
References
Marcel R Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, and Christian Sohler. StreamKM++: A clustering algorithm for data streams. Journal of Experi- mental Algorithmics (JEA), 17:2-4, 2012.
Charu C Aggarwal. A framework for diagnosing changes in evolving data streams. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 575-586. ACM, 2003.
Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approximation, In Advances in neural information processing systems, pages 10-18, 2009.
10

---

Aditya Bhaskara and Aravinda Kanchana Rwanpathirana. Robust algorithms for online k-means clustering. Algorithmic Learning Theory, pages 148-173, 2020.
Robi Bhattacharjee and Michal Moshkovitz. No-substitution k-means clustering with adversarial order. In Algorithmic Learning Theory, pages 345-366. PMLR, 2021.
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. arXiv preprint arXiv:1612.00883 2016.
Moses Charikar, Sudipto Guha, Eiva Tardos, and David B Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-16) 2002.
Moses Charikar, Liadan O' O'Callaghan, and Rina Panigrahy, Better streaming algorithms for clustering problems. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pages 30-39. ACM, 2003.
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing, 39(3):923-94) 2009. 2009.
Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996.
Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan. Clustering data streams, In Foundations of computer science, 2000. proceedings. 41st anmual symposium on, pages 359-366. IEEE, 2000.
Tom Hess and Sivan Sabato. Sequential no-substitution k-median-clusserrngg International Conference on Artificial Intelligence and Statistics, pages 962-972. PMLR, 2020.
Kumar Joag-Dev and Frank Proschan. Negative association of random variables with applications.
The Annals of Statistics, pages 286-295, 1983.
Kingsly Leung and Christopher Leckie. Unsupervised anomaly detection in network intrusion detection using clusters. In Proceedings of the Twenty-eighth Australasian conference Computer Science- Volume 38, pages 333-342. Australian Computer Society, Inc., 2005.
Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM Journal on Computing, 45(2):530-54)) 2016.
Edo Liberty, Ram Sriharsha, and Maxim Sviridenko. An algorithm for online k-means clustering. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 81-89. SIAM, 2016.
Adam Meyerson, Liadan O' callaghan, and Serge Plotkin. A k-median algorithm with running time independent of data size. Machine Learning, 56(1-3):61-87, 2004.
Michal Moshkovitz. Unexpected effects of online no-substitution k-means clustering. In Algorithmic Learning Theory, pages 892-930. PMLR, 2021.
Olfa Nasraoui, Jeff Cerwinske, Carlos Rojas, and Fabio Gonzalez. Performance of recommendation systems in dynamic streaming environments. In Proceedings of the 2007 SIAM International Conference on Data Mining, pages 569-574 SIAM, 2007.
Andriy Shepitsen, Jonathan Gemmell, Bamshad Mobasher, and Robin Burke. Personalized recom- mendation social tagging systems using hierarchical clustering. In Proceedings of the 2008 ACM conference Recommender systems, pages 259-266. ACM, 2008.
Bichen Zheng, Sang Won Yoon, and Sarah S Lam. Breast cancer diagnosis based feature extraction using a hybrid k-means and support vector machine algorithms. Expert Systems with Applications, 41(4):1477 14821148828 2014.
11


Reviews:
[{"review_id": "mTBENld9Rzg", "reviewer": "Reviewer_DQhU", "summary": "This is a theoretical paper, studying sequentially assigning points as k-median cluster centers.  \nIt assumes a random arrival order, but has no other structural assumptions.  It offers a constant factor approximation using O(k log^2 k) centers.  This improves on a recent line of work in this model removing structural assumptions and the approximation factor.  \n\nThe main idea is using geometrically increasing prefixes of the stream to estimate the k-median solution and risk, and for each using this estimate to choose centers.  A key insight is that by increasing the size of centers maintained a bit, the risk can be approximated after excluding outliers -- which turns out to be the key step in the analysis.  \n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From a theoretical perspective, the algorithm is intuitive, and is well explained by the paper, with a lot of insight.  But the bulk of the analysis is left for the supplement.  \nThe algorithm however, appears far from practical.  \nAnd as the most comparable work is an ALT 2021 paper that uses O(k log k) centers, but has approximation factor exponential in k (under all of the same model/data assumptions), I do not see the improvement as that substantial.  \n\nUltimately, I'd be ok if this paper is accepted for NeurIPS.  The work is high quality.  However, the improvement, I believe is small and theoretical, and may not have a high impact.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The random order assumption is discussed clearly.  This was useful for the paper to do.  \nThis work is unlikely to have societal impact, and it was not discussed.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "kLWxXBSdfL1", "reviewer": "Reviewer_J5wv", "summary": "The authors design a sequential random-order no-substitution algorithm for k-median clustering. Their algorithm outputs O(k\\log^2 k) centers and gives constant factor approximation with high probability. The algorithm does not depend on any assumption on the dataset and gives substantially better guarantees over earlier works.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem setup is as follows. The points to be clustered arrive one by one in a random order stream. A point arriving in a stream may or may not be chosen as a center, but if it is chosen as a center, it cannot be substituted later. The authors design a subroutine SelectProc that divides the stream into three phases, the length of each phase is a constant factor of the length of the stream. At the end of the first phase, using an offline algorithm for k-median on the points in the first phase, a set of centers is computed. This set of centers is used in the second phase to estimate the cost of clustering of the points in the second phase. In the third phase, the actual centers are selected by the subroutine. The algorithm runs O(\\log k/\\delta) instances of the subroutine SelectProc in parallel where each instance of the subroutine works on a different prefix of the stream, and the algorithm outputs all centers chosen by these subroutines. This set of centers give constant factor approximation with high probability for the k-median problem.\n\nOverall, I believe this to be a nice result for a fairly important problem. I recommend acceptance of this paper.\n\nMy only comments are regarding the writing and the presentation of the paper.\n  - Since the description of the algorithm uses a number of parameters, it would be helpful to define the notations appropriately. For example, k_+ is used in the description of the algorithm but it is defined only in Section 4.2.\n  - The authors should highlight that the performance of an algorithm in this setting is evaluated using the notion of competitive analysis of online algorithms.\n\n\n- This additional comment is to acknowledge reading author response. There is no other changes.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical in nature.", "review_text": "", "extra_scores": {"ethical_concerns": "This work is theoretical in nature. There are no serious ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ilGy9qDbvtV", "reviewer": "Reviewer_Fes6", "summary": "The paper studies $k$-median clustering in the random-order streaming model. In this particular setting, the input is randomly permuted and fed to the algorithm element by element. The input itself is a unknown finite set of points that together with a distance function forms a discrete metric space. The goal of the algorithm is to construct a clustering, by selecting a only small number of the input points as cluster centers, such that the cost of the clustering approximates the cost of an optimal $k$-median clustering of the whole space. Imposed restrictions are that the algorithm can only pick an input element as cluster center before it sees the next element and centers that have been chosen can not be substituted.\n\nThe paper contributes an algorithm that returns with high probability of success a clustering with $O(k \\log^2(k/\\delta))$ centers that approximates the cost of an optimal $k$-median clustering by a constant factor.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of the paper is interesting and has a strong practical relevance. It has already been studied in the literature and the results of the paper yield a substantial progress. Furthermore, the idea of the algorithm is novel to me and the analysis seems sound and correct (I checked the proof sketches and large parts of the proofs in the appendix).\n\nSome minor comments:\n\n- please provide the constant of the approximation in the theorem statement (something like $728$) instead of a \"universal constant $C$\"\n- large parts of the clustering community call the objective value the \"clustering cost\", I have seen that some of the related work also speak of \"clustering risk\", but you may consider switching to \"cost\" (I don't see any reason to call it risk here)\n- the symbol $\\equiv$ is used very rarely in mathematics (mainly in the context of logic) and can be substituted by $=$ in any case in your paper (standard notation improves comprehendability)\n- line 131: write $\\lvert T_{out} \\rvert = O(k \\log^2(k/\\delta))$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are adequately addressed, as the authors do, I see no direct path to negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Sk5n6CxVJ8M", "reviewer": "Reviewer_JtCc", "summary": "The paper discusses the k-median algorithm under the online, no-substitution setting. The paper considers the random order arrival of the points and obtains a constant factor approximation without requiring any structural assumptions. They provide an algorithm that gives a constant factor approximation with a $k\\log^2k$ centers assuming the $n$ is known (in the discussion they state about the use of doubling to get similar results with $\\log n$ overhead).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well structured and well written. The claims made in the paper seem sound. The problem itself is a relatively well studied theoretical problem and they manage to give a constant factor approximation algorithm that only has a $\\log^2 k$ multiplicative overhead under the random order setting, which is a relatively significant improvement on the existing research. They introduce a new concept of linear bin division to complete the analysis of the algorithm. Overall the paper looks good.\n\nQ: How does the Phase 1 and Phase 2 selection of $P_1, P_2$ (of size $\\alpha n$ each) affect the memory requirements (could it lead to memory requirement of order $n$)? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The algorithm assumes knowledge of $n$, but the paper states how to remove this with an additional $\\log n$ overhead.  They also assume random order. They leave the study of different input orders (other than random and adversarial) as a future research direction. \n\nAs the problem itself is theoretical I don’t think it creates any major negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No major ethical concerns as far as I can see.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present the first constant approximation factor on the optimal risk for k-median with no -substitution under a random arrival order model. The problem studied in the paper is an interesting problem and the authors present a simple and elegant algorithm that outperforms previous work. The only concern with the paper is that the problem may not be of interest for a wide audience. Nevertheless, after the discussion phase, all the reviewers agree that it should be accepted.
Decision: Accept (Poster)