MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Winzen, Carola		dblp
dblp
Editor(s):
Kulikov, Alexande
Vereshchagin, Nikolay		dblp
dblp
Not MPII Editor(s):
Kulikov, Alexande
Vereshchagin, Nikolay
BibTeX cite key*:
DoerrW10
Title, Booktitle
Title*:
Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity
Booktitle*:
Computer Science - Theory and Applications : 6th International Computer Science Symposium in Russia (CSR 2011)
Event, URLs
Conference URL::
http://logic.pdmi.ras.ru/csr2011/
Downloading URL:
http://www.springerlink.com/content/l81t664304473443/
Event Address*:
St. Petersburg, Russia
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
14 June 2011
Event End Date:
18 June 2011
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6651
Number:
Month:
June
Pages:
15-28
Year*:
2011
VG Wort Pages:
25
ISBN/ISSN:
978-3-642-20711-2
Sequence Number:
DOI:
10.1007/978-3-642-20712-9_2
Note, Abstract, ©
(LaTeX) Abstract:
Randomized search heuristics are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. A big step forward would be a useful complexity theory for such algorithms. We enrich the two existing black-box complexity notions due to Wegener and other authors by the restrictions that not actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems, while for others the low complexities of the previous models still hold.
Keywords:
Randomized search heuristics, black-box model
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{DoerrW10,
AUTHOR = {Doerr, Benjamin and Winzen, Carola},
 EDITOR = {Kulikov, Alexande and Vereshchagin, Nikolay},
 TITLE = {Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity},
 BOOKTITLE = {Computer Science - Theory and Applications : 6th International Computer Science Symposium in Russia (CSR 2011)},
 PUBLISHER = {Springer},
 YEAR = {2011},
 VOLUME = {6651},
 PAGES = {15--28},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {St. Petersburg, Russia},
 MONTH = {June},
 ISBN = {978-3-642-20711-2},
 DOI = {10.1007/978-3-642-20712-9_2},
}

Entry last modified by Carola Winzen, 01/15/2013
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)
[Library]		Created
03/21/2011 13:13:07
Revisions
5.
4.
3.
2.
1.		Editor(s)
Carola Winzen
Anja Becker
Carola Winzen
Carola Winzen
Carola Winzen		Edit Dates
01/15/2013 11:17:24 AM
07.02.2012 12:52:30
01/12/2012 01:19:06 PM
10/20/2011 05:41:08 PM
03/22/2011 06:52:54 PM