umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP
Computer Science Institute, University of Halle-Wittenberg, Germany.
Faculty of Economic Sciences, University of Groningen, The Netherlands, University of Economics and Business, Lviv Highway 51/2, 29016 Khmelnitsky, Ukraine and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
Department of Computer Science, Washington University, USA.
Computer Science Institute, University of Halle-Wittenberg, Germany.
2007 (English)In: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007) / [ed] J. Janssen and P. Pralat, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007, 99-111 p.Conference paper, Published paper (Refereed)
Abstract [en]

Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.

Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007. 99-111 p.
Series
Lecture Notes in Computer Science, Volume 4852
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84437ISBN: 3-540-77293-6 (print)ISBN: 978-3-540-77293-4 (print)OAI: oai:DiVA.org:umu-84437DiVA: diva2:684039
Conference
4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007)
Available from: 2014-01-07 Created: 2014-01-07 Last updated: 2014-02-12Bibliographically approved

Open Access in DiVA

No full text

Other links

http://dl.acm.org/citation.cfm?id=1778499

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 91 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf