English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Smoothed Analysis of Three Combinatorial Problems

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2E18-C Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2E1B-6
Genre: Conference Paper

Files

show Files
hide Files
:
mfcs03.ps.gz (Any fulltext), 292KB
 
File Permalink:
-
Name:
mfcs03.ps.gz
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/gzip
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Banderier, Cyril1, Author           
Beier, Rene1, Author           
Mehlhorn, Kurt1, Author           
Rovan, Branislav, Editor
Vojtáš, Peter, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2004-06-152003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 202044
Other: Local-ID: C1256428004B93B8-09CF39E77E5072D5C1256E140059E6C7-Beier2003a
 Degree: -

Event

show
hide
Title: MFCS 2003
Place of Event: Bratislava, Slovak Republic
Start-/End Date: 2003-08-25 - 2003-08-29

Legal Case

show

Project information

show

Source 1

show
hide
Title: Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 198 - 207 Identifier: ISBN: 3-540-40671-9

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2747 Sequence Number: - Start / End Page: - Identifier: -