MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kötzing, Timo
Neumann, Frank
Röglin, Heiko
Witt, Carsten		dblp
dblp
dblp
dblp
Not MPG Author(s):
Röglin, Heiko
Witt, Carsten
Editor(s):
Dorigo, Marco
Birattari, Mauro
Di Caro, Gianni A.
Doursat, René
Engelbrecht, Andries P.
Floreano, Dario
Gambardella, Luca Maria
Groß, Roderich
Sahin, Erol
Sayama, Hiroki
Stützle, Thomas		dblp
dblp
dblp
dblp
dblp
dblp
dblp
dblp
dblp
dblp
dblp
Not MPII Editor(s):
Dorigo, Marco
Birattari, Mauro
Di Caro, Gianni A.
Doursat, René
Engelbrecht, Andries P.
Floreano, Dario
Gambardella, Luca Maria
Groß, Roderich
Sahin, Erol
Sayama, Hiroki
Stützle, Thomas
BibTeX cite key*:
Koe-Neu-Roe-Wit:c:10:ACOTSP
Title, Booktitle
Title*:
Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem
Booktitle*:
Swarm Intelligence : 7th International Conference, ANTS 2010
Event, URLs
Conference URL::
Downloading URL:
http://dx.doi.org/10.1007/978-3-642-15461-4_28
Event Address*:
Brussels, Belgium
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
15 December 2010
Event End Date:
15 December 2010
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
6234
Number:
Month:
Pages:
324-335
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-3-642-15460-7
Sequence Number:
DOI:
10.1007/978-3-642-15461-4_28
Note, Abstract, ©
(LaTeX) Abstract:
Ant colony optimization (ACO) has been widely used for different combinatorial optimization problems. In this paper, we investigate ACO algorithms with respect to their runtime behavior for the traveling salesperson problem (TSP). We present a new construction graph and show that it has a stronger local property than one commonly used for constructing solutions of the TSP. Our rigorous runtime analyses for two ACO algorithms, based on these two construction procedures, show that they achieve a good approximation in expected polynomial time on random instances.
Furthermore, we point out in which situations our algorithms get trapped in local optima and show where the use of the right amount of heuristic information is provably beneficial.
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Koe-Neu-Roe-Wit:c:10:ACOTSP,
AUTHOR = {K{\"o}tzing, Timo and Neumann, Frank and R{\"o}glin, Heiko and Witt, Carsten},
 EDITOR = {Dorigo, Marco and Birattari, Mauro and Di Caro, Gianni A. and Doursat, Ren{\'e} and Engelbrecht, Andries P. and Floreano, Dario and Gambardella, Luca Maria and Groß, Roderich and Sahin, Erol and Sayama, Hiroki and St{\"u}tzle, Thomas},
 TITLE = {Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem},
 BOOKTITLE = {Swarm Intelligence : 7th International Conference, ANTS 2010},
 PUBLISHER = {Springer},
 YEAR = {2010},
 VOLUME = {6234},
 PAGES = {324--335},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Brussels, Belgium},
 ISBN = {978-3-642-15460-7},
 DOI = {10.1007/978-3-642-15461-4_28},
}

Entry last modified by Anja Becker, 01/11/2011
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/15/2010 11:54:47
Revision
1.
0.


Editor
Anja Becker
Timo Kötzing


Edit Date
11.01.2011 13:26:50
12/15/2010 11:54:47 AM