A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Fast and Memory Optimal Low-Rank Matrix Approximation
In this paper, we revisit the problem of constructing a near-optimal rank $k$ approximation of a matrix $M\in [0,1]^{m\times n}$ under the streaming data model where the columns of $M$ are revealed sequentially. We prese…
Unexpected Effects of Online no-Substitution k-means Clustering
Offline k-means clustering was studied extensively, and algorithms with a constant approximation are available. However, online clustering is still uncharted. New factors come into play: the ordering of the dataset and w…
ClusteringOnline ClusteringBeyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and $k$-System Constraints
In this paper, we study the non-monotone adaptive submodular maximization problem subject to a knapsack and a $k$-system constraints. The input of our problem is a set of items, where each item has a particular state dra…
2kFinite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equili…
Approximation Guarantees for Adaptive Sampling
In this paper we analyze an adaptive sampling approach for submodular maximization. Adaptive sampling is a technique that has recently been shown to achieve a constant factor approximation guarantee for submodular m…