Smoothed Analysis of Three Combinatorial Problems

Banderier, Cyril; Beier, Rene; Mehlhorn, Kurt; Rovan, Branislav; Vojtáš, Peter

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Smoothed Analysis of Three Combinatorial Problems

MPS-Authors

/persons/resource/persons44063

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

/persons/resource/persons44108

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

/persons/resource/persons45021

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

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-2E18-C

要旨

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.