TY - GEN A1 - Büsing, Christina T1 - Recoverable Robust Shortest Path Problems N2 - In this paper we investigate two different recoverable robust models to deal with cost uncertainties in a shortest path problem. Recoverable robustness extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen. Thus, the parameter k can be interpreted as a mediator between robust optimization - no changes allowed - and optimization on the fly - an arbitrary solution can be chosen. Considering three classical scenario sets, which model uncertainties in the cost function, we show that this new problem is strongly NP-hard in all these cases and is not approximable, unless P=NP. This is in contrast to the robust shortest path problem, where, for example, an optimal solution can be computed efficiently for interval and Gamma-scenarios. For series-parallel graphs and interval scenarios, we present a polynomial time algorithm for this recoverable robust setting. In our second model the recovery set, i.e., the set of paths selectable in the second stage is not limited, but deviating from the previous choice comes at extra cost. Thus, a path chosen in the first stage produces renting costs modeled as an alpha-fraction of the scenario cost. For an arc taken in the second stage the remaining cost needs to be paid in addition to some extra inflation cost modeled by a beta-fraction of the scenario cost, if the arc was not reserved beforehand. The complexity status of this problem is similar to the robust case. Yet, for Gamma-scenarios the problem is again strongly NP-hard, but can be approximated. KW - Shortest Paths KW - Robust Optimization KW - Recovery Y1 - 2012 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1022 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-10225 ER -