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, 97-104 p.Conference 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. 97-104 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-60839OAI: oai:DiVA.org:kth-60839DiVA: 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: 2016-05-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Full-text in kedrigern.dcs

Search in DiVA

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

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