2013 | OriginalPaper | Buchkapitel
The Online Replacement Path Problem
verfasst von : David Adjiashvili, Gianpaolo Oriolo, Marco Senatore
Erschienen in: Algorithms – ESA 2013
Verlag: Springer Berlin Heidelberg
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
We study a new robust path problem, the
Online Replacement Path problem (ORP)
. Consider the problem of routing a physical package through a faulty network
G
= (
V
,
E
) from a source
s
∈
V
to a destination
t
∈
V
as quickly as possible. An adversary, whose objective is to maximize the latter routing time, can choose to remove a single edge in the network. In one setup, the identity of the edge is revealed to the routing mechanism (RM) while the package is in
s
. In this setup the best strategy is to route the package along the shortest path in the remaining network. The payoff maximization problem for the adversary becomes the
Most Vital Arc problem (MVA)
, which amounts to choosing the edge in the network whose removal results in a maximal increase of the
s
-
t
distance. However, the assumption that the RM is informed about the failed edge when standing at
s
is unrealistic in many applications, in which failures occur
online
, and, in particular, after the routing has started. We therefore consider the setup in which the adversary can reveal the identity of the failed edge just before the RM attempts to use this edge, thus forcing it to use a different route to
t
, starting from the current node. The problem of choosing the nominal path minimizing the worst case arrival time at
t
in this setup is ORP. We show that ORP can be solved in polynomial time and study other models naturally providing middle grounds between MVA and ORP. Our results show that ORP comprises a highly flexible and tractable framework for dealing with robustness issues in the design of RM-s.