@inproceedings{43fbb03d21f4439e9835a371add275b8,
title = "Computing single source shortest paths using single-objective fitness functions",
abstract = "Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem. Scharnow, Tin-nefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multi-objective approach.",
keywords = "Algorithms, Performance, Theory",
author = "Surender Baswana and Somenath Biswas and Benjamin Doerr and Tobias Friedrich and Kurur, \{Piyush P.\} and Frank Neumann",
year = "2009",
month = sep,
day = "21",
doi = "10.1145/1527125.1527134",
language = "English",
isbn = "9781605584140",
series = "Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09",
pages = "59--65",
booktitle = "Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09",
note = "10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09 ; Conference date: 09-01-2009 Through 11-01-2009",
}