Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s, t)-Cuts
Ist Teil von
Approximation and Online Algorithms, 2020, Vol.11926, p.29-42
Ort / Verlag
Switzerland: Springer International Publishing AG
Erscheinungsjahr
2020
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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 \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$2k+1$$\end{document}. reposition and comparison strategies achieve this bound.
We refine this analysis by focusing on graphs with a maximum (s, t)-cut size \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\mu _{\text {max}}$$\end{document} less than k. A strategy called detour is proposed and its competitive ratio is \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$2\mu _{\text {max}}+ \sqrt{2}(k-\mu _{\text {max}}) + 1$$\end{document} when \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\mu _{\text {max}}< k$$\end{document} which is strictly less than \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$2k+1$$\end{document}. Moreover, when \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\mu _{\text {max}}\ge k$$\end{document}, the competitive ratio of detour is \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$2k+1$$\end{document} and is optimal. Therefore, detour improves the competitiveness of the deterministic strategies known up to now.