Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts
verfasst von : Pierre Bergé, Lou Salaün
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The k-Canadian Traveller Problem consists in finding the optimal way from a source s to a target t on an undirected weighted graph G, knowing that at most k edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least \(2k+1\). reposition and comparison strategies achieve this bound.
We refine this analysis by focusing on graphs with a maximum (s, t)-cut size \(\mu _{\text {max}}\) less than k. A strategy called detour is proposed and its competitive ratio is \(2\mu _{\text {max}}+ \sqrt{2}(k-\mu _{\text {max}}) + 1\) when \(\mu _{\text {max}}< k\) which is strictly less than \(2k+1\). Moreover, when \(\mu _{\text {max}}\ge k\), the competitive ratio of detour is \(2k+1\) and is optimal. Therefore, detour improves the competitiveness of the deterministic strategies known up to now.