The power of recourse for online MST and TSP

Nicole Megow, Martin Skutella, José Verschae, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

Abstract

We consider the online MST and TSP problems with recourse. The nodes of an unknown graph with metric edge cost appear one by one and must be connected in such a way that the resulting tree or tour has low cost. In the standard online setting, with irrevocable decisions, no algorithm can guarantee a constant competitive ratio. In our model we allow recourse actions by giving a limited budget of edge rearrangements per iteration. It has been an open question for more than 20 years if an online algorithm equipped with a constant (amortized) budget can guarantee constant-approximate solutions [7]. As our main result, we answer this question affirmatively in an amortized setting. We introduce an algorithm that maintains a nearly optimal tree when given constant amortized budget. In the non-amortized setting, we specify a promising proof technique and conjecture a structural property of optimal solutions that would prove a constant competitive ratio with a single recourse action. It might seem rather optimistic that such a small budget should be sufficient for a significant cost improvement. However, we can prove such power of recourse in the offline setting in which the sequence of node arrivals is known. Even this problem prohibits constant approximations if there is no recourse allowed. Surprisingly, already a smallest recourse budget significantly improves the performance guarantee from non-constant to constant. Unlike in classical TSP variants, the standard double-tree and shortcutting approach does not give constant guarantees in the online setting. However, a non-trivial robust shortcutting technique allows to translate online MST results into TSP results at the loss of small factors.

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages689-700
Number of pages12
EditionPART 1
DOIs
StatePublished - 2012
Externally publishedYes
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: 9 Jul 201213 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period9/07/1213/07/12

Fingerprint

Dive into the research topics of 'The power of recourse for online MST and TSP'. Together they form a unique fingerprint.

Cite this