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 |
|