Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.mfcs.sk/mfcs2003/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 05:21:57 PM
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