2 papers
cs.DS2009
On Smoothed Analysis of Quicksort and Hoare's Find
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey +1
We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implem…
cs.DS2009★ 15 cited
k-Means has Polynomial Smoothed Complexity
David Arthur, Bodo Manthey, Heiko Röglin
The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential wors…