Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Approximation hardness of the traveling salesman reoptimization problem
ETH Zurich.
ETH Zurich.
2007 (English)In: Proceedings of the 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007), 2007, p. 97-104Conference paper, Published paper (Refereed)
Abstract [en]

In TSP reoptimization, a complete weighted graph and an optimal Hamiltonian tour are given; the problem is to find an optimal solution for a locally modified input. In this paper, we consider the local modification where one edge of the graph becomes cheaper. We show that the best approximation ratio known so far that is achievable by polynomial-time algorithms heavily depends on various parameters. We show that for a wide range of parameters the approximation ratio is improved. Moreover, these parameters limit the class of hard instances, which might help to find better approximation algorithms also for the general case.

Place, publisher, year, edition, pages
2007. p. 97-104
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-60839OAI: oai:DiVA.org:kth-60839DiVA, id: diva2:478017
Conference
3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007), October 26-28, 2007, Znojmo, Czech Republic
Note

QC 20120118

Available from: 2012-01-15 Created: 2012-01-15 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Full-text in kedrigern.dcs

Search in DiVA

By author/editor
Mömke, Tobias
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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