Smoothed analysis: analysis of algorithms beyond worst case

Manthey, Bodo and Röglin, Heiko (2011) Smoothed analysis: analysis of algorithms beyond worst case. it - Information Technology, 53 (6). pp. 280-286. ISSN 1611-2776

PDF
Restricted to UT campus only: Request a copy
271Kb

Abstract:	Many algorithms perform very well in practice, but have a poor worst-case performance. The reason for this discrepancy is that worst-case analysis is often a way too pessimistic measure for the performance of an algorithm. In order to provide a more realistic performance measure that can explain the practical performance of algorithms, smoothed analysis has been introduced. It is a hybrid of the classical worst-case analysis and average-case analysis, where the performance on inputs is measured that are subject to random noise. We give a gentle, not too formal introduction to smoothed analysis by means of two examples: the k-means method for clustering and the Nemhauser/Ullmann algorithm for the knapsack problem.
Item Type:	Article
Copyright:	© 2011 Oldenbourg Verlag
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/78736
Official URL:	http://dx.doi.org/10.1524/itit.2011.0654
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page