Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 26, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: https://ethz.zoom.us/j/563801169
Speaker: Julian Portmann
The talk was recorded. Use the following link to access it:https://ethz.zoom.us/rec/share/wPd3EpLNxkBITZXUr2H2au0wMIDEaaa8gSIY_KcOmEolghzOOdaSdAv7oyCjFQCc?startTime=1585220123000
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this work, we improve their analysis to show that, for any arbitrarily small constant ε > 0, with only εk additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.
Joint work with Davin Choo, Christoph Grunau, and Václav Rozhoň.
Automatic MiSe System Software Version 1.4803M | admin login