Smoothed Analysis of Local Search Algorithms

Manthey, B. (Invited speaker)

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: null
Event typeConference
Conference number14
LocationVictoria, Canada, British Columbia
Degree of RecognitionInternational