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
Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
Computer Science Institute, University of Halle-Wittenberg, Germany.
Computer Science Institute, University of Halle-Wittenberg, Germany.
2008 (English)In: Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008) / [ed] B. Yang, D.-Z. Du and C.A. Wang, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2008, 211-224 p.Conference paper, Published paper (Refereed)
Abstract [en]

We introduce a new combinatorial optimization problem, which is a generalization of the Traveling Salesman Problem (TSP) and which we call Traveling Salesman Problem of Second Order (2-TSP). It is motivated by an application in bioinformatics, especially the Permuted Variable Length Markov model. We propose seven elementary heuristics and two exact algorithms for the 2-TSP, some of which are generalizations of similar algorithms for the Asymmetric Traveling Salesman Problem (ATSP), some of which are new ideas. Finally we experimentally compare the algorithms for random instances and real instances from bioinformatics. Our experiments show that for the real instances most heuristics lead to optimum or almost-optimum solutions, and for the random instances the exact algorithms need less time than for the real instances.

Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2008. 211-224 p.
Series
Lecture Notes in Computer Science, Volume 5165
Keyword [en]
Traveling Salesman Problem, Assignment Problem, Traveling Salesman Problem of Second Order, Heuristic, Exact Algorithm
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84445OAI: oai:DiVA.org:umu-84445DiVA: diva2:684091
Conference
2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008)
Available from: 2014-01-07 Created: 2014-01-07 Last updated: 2014-12-19Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Jäger, Gerold

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 29 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