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:




Library Locked Library locked




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

URL of the conference:

http://logic.pdmi.ras.ru/csr2011/

URL for downloading the paper:

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
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)
[Library]
Created
03/21/2011 01:13:07 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section