Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • 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 (engelsk)Inngår i: 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, s. 99-111Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007. s. 99-111
Serie
Lecture Notes in Computer Science ; Volume 4852
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-84437ISBN: 3-540-77293-6 (tryckt)ISBN: 978-3-540-77293-4 (tryckt)OAI: oai:DiVA.org:umu-84437DiVA, id: diva2:684039
Konferanse
4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007)
Tilgjengelig fra: 2014-01-07 Laget: 2014-01-07 Sist oppdatert: 2018-06-08bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

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

Person

Jäger, Gerold

Søk i DiVA

Av forfatter/redaktør
Jäger, Gerold

Søk utenfor DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 400 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf