13/04/2021

Consistent k-median: Simpler, better and robust

Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian

Keywords:

Abstract Paper Similar Papers

Abstract: 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 [18]. We show that a simple local-search based on-line 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 [18].

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AISTATS 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 23:50 
 0
 0
 0
 0
 19:23 
 0
 0
 0
 0
 11:40 
 0
 0
 0
 0
 17:30 
 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 17:42 
 0
 0
 0
 0
 16:31 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 24:22 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 24:57 
 0
 0
 0
 0
 3:27 
 0
 0
 0
 0
 5:39 
 0
 0
 0
 0
 3:03 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 14:49 
 0
 0
 0
 0
 11:10 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 13:46 
 0
 0
 0
 0
 25:10 
 0
 0
 0
 0
 3:13 
 0
 1
 1
 1
 5:22 
 0
 0
 0
 0
 12:52 
 0
 0
 0
 1
 15:56 
 0
 0
 0
 0
 10:22 
 0
 0
 0
 0
 3:21 
 0
 0
 0
 0
 21:08 
 0
 0
 0
 0
 13:51 
 0
 0
 0
 0
 16:56 
 0
 0
 0
 0
 13:51 
 0
 0
 0
 0
 25:27 
 0
 0
 0
 0
 14:15 
 0
 0
 0
 0
 15:31 
 0
 0
 0
 0
 14:25 
 0
 0
 0
 0
 2:50 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 2:52 
 0
 0
 0
 0
 15:02 
 0
 0
 1
 1
 3:21