Consistent $k$-Median: Simpler, Better and Robust
In this paper we introduce and study the online consistent $k$-clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvitskii, ICML17]. We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with $O(k^2 \log^2 (nD))$ swaps of medians (recourse) in total, where $D$ is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of [Lattanzi-Vassilvitskii, ICML17].
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Median of Means Sampling for the Keister Function
This study investigates the performance of median-of-means sampling compared to traditional mean-of-means sampling for computing the Keister function integral using Randomized Quasi-Monte Carlo (RQMC) methods. The resear…
Numerical IntegrationUniversal Weak Coreset
Coresets for $k$-means and $k$-median problems yield a small summary of the data, which preserve the clustering cost with respect to any set of $k$ centers. Recently coresets have also been constructed for constrained $k…
ClusteringConstrained ClusteringData CompressionDriven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise, Interestingness, Attention, Curiosity, Creativity, Art, Science, Music, Jokes
I argue that data becomes temporarily interesting by itself to some self-improving, but computationally limited, subjective observer once he learns to predict or compress the data in a better way, thus making it subjecti…
Weighted Mean and Median graph Filters with Attenuation Factor for Sensor Network
This paper proposes a weighted attenuation k-hop graph, which depicts the spatial neighbor nodes with their hops from the central node. Based on this k-kop graph, we further propose a node selecting graph, which selects …
DenoisingAdvertiser Learning in Direct Advertising Markets
Direct buy advertisers procure advertising inventory at fixed rates from publishers and ad networks. Such advertisers face the complex task of choosing ads amongst myriad new publisher sites. We offer evidence that adver…
counterfactual