Article ID: | iaor20172784 |
Volume: | 34 |
Issue: | 2 |
Start Page Number: | 554 |
End Page Number: | 573 |
Publication Date: | Aug 2017 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Kasperski Adam, Zielinski Pawel, Hradovich Mikita |
Keywords: | combinatorial optimization, heuristics |
This paper deals with the recoverable robust spanning tree problem under interval uncertainty representations. A strongly polynomial time, combinatorial algorithm for the recoverable spanning tree problem is first constructed. This problem generalizes the incremental spanning tree problem, previously discussed in literature. The algorithm built is then applied to solve the recoverable robust spanning tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm allows to obtain several approximation results for the recoverable robust spanning tree problem under the Bertsimas and Sim interval uncertainty representation and the interval uncertainty representation with a budget constraint.