Journal Article
@Article
Artikel in Fachzeitschrift


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(s)

Author(s):

Doerr, Benjamin
Winzen, Carola

dblp
dblp



BibTeX cite key*:

DoerrW12Ranking

Title

Title*:

Ranking-Based Black-Box Complexity

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://link.springer.com/journal/453

Download URL
for the article:

http://link.springer.com/article/10.1007%2Fs00453-012-9684-9

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer.com/?SGWID=5-102-0-0-0

Publisher's
Address:


ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

?

Number:


Publishing Date:

2014

Pages*:

?

Number of
VG Pages:

68

Page Start:


Page End:


Sequence Number:


DOI:

10.1007/s00453-012-9684-9

Note, Abstract, ©

Note:

To appear.

(LaTeX) Abstract:

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field.
While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed.
We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms.

We show that the new ranking-based model can give more realistic complexity estimates. The class of all binary-value functions has a black-box complexity of $O(\log n)$ in the previous black-box models, but has a ranking-based complexity of $\Theta(n)$.

On the other hand, for the class of all \onemax functions, we present a ranking-based black-box algorithm that has a runtime of $\Theta(n / \log n)$, which shows that the \onemax problem does not become harder with the additional ranking-basedness restriction.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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:

@ARTICLE{DoerrW12Ranking,
AUTHOR = {Doerr, Benjamin and Winzen, Carola},
TITLE = {Ranking-Based Black-Box Complexity},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2014},
VOLUME = {?},
PAGES = {?},
ISBN = {0178-4617},
DOI = {10.1007/s00453-012-9684-9},
NOTE = {To appear.},
}


Entry last modified by Benjamin Doerr, 05/20/2014
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
12/07/2012 12:38:14 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Benjamin Doerr
Uwe Brahm
Benjamin Doerr
Benjamin Doerr
Benjamin Doerr
Edit Dates
01/01/2014 11:43:12 PM
01-02-2013 02:39:40 PM
01/11/2013 11:25:34 AM
01/02/2013 12:00:45 AM
12/07/2012 12:38:14 PM