Change search
ReferencesLink to record
Permanent link

Direct link
Worst case performance of an approximation algorithm for asymmetric TSP
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: STACS 2004, PROCEEDINGS, BERLIN: SPRINGER , 2004, Vol. 2996, 465-476 p.Conference paper (Refereed)
Abstract [en]

In 1982 Frieze, Galbiati and Maffioli (Networks 12:23-39) published their famous algorithm for approximating the TSP tour in an asymmetric graph with triangle inequality. They show that the algorithm approximates the TSP tour within a factor of log(2) n. We construct a family of graphs for which the algorithm (with some implementation details specified by us) gives an approximation which is log(2) n/(2 + 2epsilon) times the optimum solution. This shows that the analysis by Frieze et al. is tight up to a constant factor and can hopefully give deeper understanding of the problem and new ideas in developing an improved approximation algorithm.

Place, publisher, year, edition, pages
BERLIN: SPRINGER , 2004. Vol. 2996, 465-476 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 2996
National Category
Computer Science
URN: urn:nbn:se:kth:diva-43981ISI: 000189497100041ScopusID: 2-s2.0-33846193855ISBN: 3-540-21236-1OAI: diva2:450879
21st Annual Symposium on Theoretical Aspects of Computer Science. Montpellier, FRANCE. MAR 25-27, 2004
QC 20111024Available from: 2011-10-24 Created: 2011-10-19 Last updated: 2011-10-24Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Palbom, Anna
By organisation
Numerical Analysis and Computer Science, NADA
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link