Smoothed Analysis of Local Search Algorithms

Bodo Manthey

doi:10.1007/978-3-319-21840-3_43

Smoothed Analysis of Local Search Algorithms

Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

1 Citation (Scopus)

11 Downloads (Pure)

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 language	Undefined
Title of host publication	Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)
Editors	Frank Dehne, Jörg-Rüdiger Sack, Ulrike Stege
Place of Publication	London
Publisher	Springer
Pages	518-527
Number of pages	10
ISBN (Print)	978-3-319-21839-7
DOIs	https://doi.org/10.1007/978-3-319-21840-3_43
Publication status	Published - 5 Aug 2015
Event	14th International Symposium on Algorithms and Data Structures 2015 - University of Victoria, Victoria, Canada Duration: 5 Aug 2015 → 7 Aug 2015 Conference number: 14 https://wads2015.cs.uvic.ca/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9214
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Algorithms and Data Structures 2015
Abbreviated title	WADS 2015
Country/Territory	Canada
City	Victoria
Period	5/08/15 → 7/08/15
Internet address	https://wads2015.cs.uvic.ca/

Keywords

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

Access to Document

10.1007/978-3-319-21840-3_43

http://eprints.eemcs.utwente.nl/secure2/25930/01/WADS2015_Manthey_LocalSearch.pdf

Cite this

@inproceedings{7708d5f2d3f346b997254cc584f6d49c,

title = "Smoothed Analysis of Local Search Algorithms",

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.",

keywords = "EWI-25930, IR-96737, METIS-312549, local search heuristics, Smoothed Analysis",

author = "Bodo Manthey",

note = "10.1007/978-3-319-21840-3\_43 ; 14th International Symposium on Algorithms and Data Structures 2015 ; Conference date: 05-08-2015 Through 07-08-2015",

year = "2015",

month = aug,

day = "5",

doi = "10.1007/978-3-319-21840-3\_43",

language = "Undefined",

isbn = "978-3-319-21839-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "518--527",

editor = "Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Ulrike Stege",

booktitle = "Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)",

address = "Germany",

url = "https://wads2015.cs.uvic.ca/",

}

Manthey, B 2015, Smoothed Analysis of Local Search Algorithms. in F Dehne, J-R Sack & U Stege (eds), Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015). Lecture Notes in Computer Science, vol. 9214, Springer, London, pp. 518-527, 14th International Symposium on Algorithms and Data Structures 2015, Victoria, British Columbia, Canada, 5/08/15. https://doi.org/10.1007/978-3-319-21840-3_43

Smoothed Analysis of Local Search Algorithms. / Manthey, Bodo.
Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015). ed. / Frank Dehne; Jörg-Rüdiger Sack; Ulrike Stege. London: Springer, 2015. p. 518-527 (Lecture Notes in Computer Science; Vol. 9214).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Smoothed Analysis of Local Search Algorithms

AU - Manthey, Bodo

N1 - Conference code: 14

PY - 2015/8/5

Y1 - 2015/8/5

N2 - 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.

AB - 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.

KW - EWI-25930

KW - IR-96737

KW - METIS-312549

KW - local search heuristics

KW - Smoothed Analysis

U2 - 10.1007/978-3-319-21840-3_43

DO - 10.1007/978-3-319-21840-3_43

M3 - Conference contribution

SN - 978-3-319-21839-7

T3 - Lecture Notes in Computer Science

SP - 518

EP - 527

BT - Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015)

A2 - Dehne, Frank

A2 - Sack, Jörg-Rüdiger

A2 - Stege, Ulrike

PB - Springer

CY - London

T2 - 14th International Symposium on Algorithms and Data Structures 2015

Y2 - 5 August 2015 through 7 August 2015

ER -