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
On the Hardness of Reoptimization
ETH Zurich.
ETH Zurich.
ETH Zurich.
ETH Zurich.
2008 (English)In: SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings / [ed] Viliam Geffert, Alberto Bertoni, Berlin, Heidelberg: Springer Berlin/Heidelberg, 2008, Vol. 4910, 50-65 p.Conference paper, Published paper (Refereed)
Abstract [en]

We consider the following reoptimization scenario: Given an instance of an optimization problem together with an optimal solution, we want to find a high-quality solution for a locally modified instance. The naturally arising question is whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. In this paper, we survey some partial answers to this questions: Using some variants of the traveling salesman problem and the Steiner tree problem as examples, we show that the answer to this question depends on the considered problem and the type of local modification and can be totally different: For instance, for some reoptimization variant of the metric TSP, we get a 1.4-approximation improving on the best known approximation ratio of 1.5 for the classical metric TSP. For the Steiner tree problem on graphs with bounded cost function, which is APX-hard in its classical formulation, we even obtain a PTAS for the reoptimization variant. On the other hand, for a variant of TSP, where some vertices have to be visited before a prescribed deadline, we are able to show that the reoptimization problem is exactly as hard to approximate as the original problem.

Place, publisher, year, edition, pages
Berlin, Heidelberg: Springer Berlin/Heidelberg, 2008. Vol. 4910, 50-65 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9742 ; 4910
Keyword [en]
reoptimization, hardness
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-52364DOI: 10.1007/978-3-540-77566-9_5ISBN: 978-3-540-77565-2 (print)OAI: oai:DiVA.org:kth-52364DiVA: diva2:466332
Conference
Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008
Projects
SBF grant C 06.0108 as part of the COST 293 (GRAAL)
Note
QC 20120113Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2012-01-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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