Smoothed Analysis of Local Search Algorithms

Activity: Talk or presentationInvited talk


Smoothed analysis is a method for analyzing the performance of algorithms for which classical worst-case analysis fails to explain the performance observed in practice. Smoothed analysis has been applied to explain the performance of a variety of algorithms in the last years.

One particular class of algorithms where smoothed analysis has been used successfully are local search algorithms. We give a survey of smoothed analysis, in particular applied to local search algorithms.
Period5 Aug 20157 Aug 2015
Event title14th International Symposium on Algorithms and Data Structures 2015
Event typeConference
Conference number14
LocationVictoria, Canada, British Columbia
Degree of RecognitionInternational