Inhalt des Dokuments
Preprint 34-2008
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Recoverable Robust Shortest Path Problems
- Author
- Classification
-
not available
- Keywords
-
recoverable robustness, shortest path
- Abstract
-
Recoverable robustness is a concept to avoid over-conservatism in robust optimization by allowing a limited recovery after the full data is revealed.We investigate two settings of recoverable robust shortest path problems. In both settings the costs of the arcs are subject to uncertainty. For the first setting, at most k arcs of the chosen path can be altered in the recovery. In the second setting, we commit ourselves to a path before the costs are fully known. Deviating from this choice in the recovery comes at extra costs. For each setting we consider three different classes of scenarios sets.We show that both problems are NP-hard. For the second setting we give an approximation algorithm depending on the inflation factor and the so-called rental factor.
- Source
- Download as [PDF]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe