Recoverable robust spanning tree problem under interval uncertainty representations

Recoverable robust spanning tree problem under interval uncertainty representations

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.