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
Kötzing, Timo
Lengler, Johannes
Winzen, Carola

dblp
dblp
dblp
dblp

Not MPG Author(s):

Lengler, Johannes

BibTeX cite key*:

DoerrKLW13

Title

Title*:

Black-Box Complexities of Combinatorial Problems

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.journals.elsevier.com/theoretical-computer-science

Download URL
for the article:

http://www.sciencedirect.com/science/article/pii/S0304397512009681

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:


ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

471

Number:


Publishing Date:

2013

Pages*:

84-106

Number of
VG Pages:

90

Page Start:

84

Page End:

106

Sequence Number:


DOI:

10.1016/j.tcs.2012.10.039

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Black-box complexity, counting the number of queries needed to find the optimum of a problem without having access to an explicit problem description, was introduced by Droste, Jansen, and Wegener (Theory of Computing Systems
39 (2006) 525--544) to measure the difficulty of solving an optimization problem via generic search heuristics such as evolutionary algorithms, simulated annealing or ant colony optimization.

Since then, a number of similar complexity notions were introduced. However, so far these new notions were only analyzed for artificial test problems. In this paper, we move a step forward and analyze the different black-box complexity notions for two classic combinatorial problems, namely the minimum spanning tree and the single-source shortest path problem. Besides proving bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem has a significant influence on its black-box complexity. In addition, when regarding the unbiased (symmetry-invariant) black-box complexity of combinatorial problems, it is important to choose a meaningful definition of unbiasedness.

URL for the Abstract:


Categories,
Keywords:

Black-box complexity, Runtime analysis, Combinatorial optimization, Theory

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:

VGWort pages by Benjamin

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{DoerrKLW13,
AUTHOR = {Doerr, Benjamin and K{\"o}tzing, Timo and Lengler, Johannes and Winzen, Carola},
TITLE = {Black-Box Complexities of Combinatorial Problems},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2013},
VOLUME = {471},
PAGES = {84--106},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2012.10.039},
}


Entry last modified by Benjamin Doerr, 02/17/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:47:17 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Benjamin Doerr
Anja Becker
Uwe Brahm
Benjamin Doerr
Benjamin Doerr
Edit Dates
01/01/2014 10:51:04 PM
01.02.2013 15:11:41
01-02-2013 02:38:44 PM
01/11/2013 11:24:46 AM
12/07/2012 12:47:17 PM