MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Banderier, Cyril
Beier, Rene
Mehlhorn, Kurt		dblp
dblp
dblp
Editor(s):
Rovan, Branislav
Vojtas, Peter		dblp
dblp
Not MPII Editor(s):
Rovan, Branislav
Vojtas, Peter
BibTeX cite key*:
Beier2003a
Title, Booktitle
Title*:
Smoothed Analysis of Three Combinatorial Problems
Booktitle*:
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Event, URLs
Conference URL::
http://www.mfcs.sk/mfcs2003/
Downloading URL:
http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=2747&spage=198
http://www.mpi-sb.mpg.de/~rbeier/mfcs03.ps.gz
Event Address*:
Bratislava, Slovak Republic
Language:
English
Event Date*
(no longer used):
August, 25 - August, 29
Organization:
European Association for Theoretical Computer Science
Event Start Date:
25 August 2003
Event End Date:
29 August 2003
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2747
Number:
Month:
Pages:
198-207
Year*:
2003
VG Wort Pages:
25
ISBN/ISSN:
3-540-40671-9
Sequence Number:
DOI:
10.1007/b11836
Note, Abstract, ©
(LaTeX) 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.
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/mfcs/mfcs2003.html#BanderierBM03
Download
Access Level:
Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Beier2003a,
AUTHOR = {Banderier, Cyril and Beier, Rene and Mehlhorn, Kurt},
 EDITOR = {Rovan, Branislav and Vojtas, Peter},
 TITLE = {Smoothed Analysis of Three Combinatorial Problems},
 BOOKTITLE = {Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003},
 PUBLISHER = {Springer},
 YEAR = {2003},
 ORGANIZATION = {European Association for Theoretical Computer Science},
 VOLUME = {2747},
 PAGES = {198--207},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bratislava, Slovak Republic},
 ISBN = {3-540-40671-9},
 DOI = {10.1007/b11836},
}

Entry last modified by Anja Becker, 01/07/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rene Beier		Created
01/07/2004 17:21:57
Revisions
14.
13.
12.
11.
10.		Editor(s)
Anja Becker
Christine Kiesel
Tamara Hausmann
Ulrich Meyer
Ulrich Meyer		Edit Dates
07.01.2008 10:27:59
03.10.2006 20:58:57
13.06.2006 12:47:10
03/30/2005 07:01:32 PM
15.06.2004 14:47:42