de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Smoothed Analysis of Three Combinatorial Problems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44063

Banderier,  Cyril
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44108

Beier,  Rene
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Banderier, C., Beier, R., & Mehlhorn, K. (2003). Smoothed Analysis of Three Combinatorial Problems. In Mathematical foundations of computer science 2003: 28th International Symposium, MFCS 2003 (pp. 198-207). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2E18-C
Abstract
Smoothed analysis combines elements over worst-case and average case analysis. For an instance $x$, the smoothed complexity is the average complexity of an instance obtained from $x$ by a perturbation. The smoothed complexity of a problem is the worst smoothed complexity of any instance. Spielman and Teng introduced this notion for continuous problems. We apply the concept to combinatorial problems and study the smoothed complexity of three classical discrete problems: quicksort, left-to-right maxima counting, and shortest paths.