English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Journal Article

Black-Box Complexities of Combinatorial Problems

MPS-Authors
/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44814

Kötzing,  Timo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44908

Lengler,  Johannes
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45750

Doerr,  Carola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Doerr, B., Kötzing, T., Lengler, J., & Doerr, C. (2013). Black-Box Complexities of Combinatorial Problems. Theoretical Computer Science, 471, 84-106. doi:10.1016/j.tcs.2012.10.039.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0015-3C1F-C
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.