Smoothed Analysis of Local Search Algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

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.
Original languageUndefined
Title of host publicationProceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)
EditorsFrank Dehne, Jörg-Rüdiger Sack, Ulrike Stege
Place of PublicationLondon
PublisherSpringer
Pages518-527
Number of pages10
ISBN (Print)978-3-319-21839-7
DOIs
Publication statusPublished - 5 Aug 2015
Event14th International Symposium on Algorithms and Data Structures 2015 - University of Victoria, Victoria, Canada
Duration: 5 Aug 20157 Aug 2015
Conference number: 14
https://wads2015.cs.uvic.ca/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9214
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Symposium on Algorithms and Data Structures 2015
Abbreviated titleWADS 2015
CountryCanada
CityVictoria
Period5/08/157/08/15
Internet address

Keywords

  • EWI-25930
  • IR-96737
  • METIS-312549
  • local search heuristics
  • Smoothed Analysis

Cite this