Improved smoothed analysis of the means method
Manthey, Bodo and Röglin, Heiko (2009) Improved smoothed analysis of the means method. In: Proceedings of the 20th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2009, 46 Jan 2009, New York, NY, USA (pp. pp. 461470).

PDF
262kB 
Abstract:  The means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worstcase runningtime, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii aimed at closing this gap, and they proved a bound of poly() on the smoothed runningtime of the means method, where is the number of data points and is the standard deviation of the Gaussian perturbation. This bound, though better than the worstcase bound, is still much larger than the runningtime observed in practice.
We improve the smoothed analysis of the means method by showing two upper bounds on the expected runningtime of means. First, we prove that the expected runningtime is bounded by a polynomial in and Second, we prove an upper bound of poly(), where is the dimension of the data space. The polynomial is independent of and , and we obtain a polynomial bound for the expected runningtime for Finally, we show that means runs in smoothed polynomial time for onedimensional instances. 
Item Type:  Conference or Workshop Item 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/68852 
Official URL:  http://www.siam.org/proceedings/soda/2009/SODA09_051_mantheyb.pdf 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page