The recoverable robust spanning tree problem with interval costs is polynomially solvable

DOI10.1007/S11590-016-1057-XMaRDI QIDQ2361123zbMATH OpenOpenAlexWikidataFDO

Authors Mikita Hradovich, Adam Kasperski, Paweł Zieliński

Publication date 29 June 2017

Published in Optimization Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1602.07422

zbMATH Keywords

robust optimizationinterval datamatroidsspanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15) Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: In this paper the robust recoverable spanning tree problem with interval edge costs is considered. The complexity of this problem has remained open to date. It is shown that the problem is polynomially solvable, by using an iterative relaxation method. A generalization of this idea to the robust recoverable matroid basis problem is also presented. Polynomial algorithms for both robust recoverable problems are proposed.

Recommendations

• Recoverable robust spanning tree problem under interval uncertainty representations
• The robust spanning tree problem with interval data
• The robust fractional spanning tree problem with interval data
• A branch and bound algorithm for the robust spanning tree problem with interval data
• Recoverable Robust Combinatorial Optimization Problems

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Incremental network optimization: theory and algorithms
• Iterative methods in combinatorial optimization.
• Matroids and the greedy algorithm
• Network flows. Theory, algorithms, and applications.
• On the approximability of robust spanning tree problems
• On the recoverable robust traveling salesman problem
• Recoverable Robust Combinatorial Optimization Problems
• Recoverable robust knapsacks: the discrete scenario case
• Recoverable robust shortest path problems
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Testing membership in matroid polyhedra
• The concept of recoverable robustness, linear programming recovery, and railway applications

Cited in

(14)

• A linear time algorithm for the robust recoverable selection problem
• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• Recoverable robust prize-collecting call control problem
• On the enumeration of non-dominated spanning trees with imprecise weights
• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
• Matroid bases with cardinality constraints on the intersection
• Recoverable robust spanning tree problem under interval uncertainty representations
• A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
• Recoverable robust representatives selection problems with discrete budgeted uncertainty
• On the enumeration of non-dominated matroids with imprecise weights
• Recoverable robust shortest path problem under interval budgeted uncertainty representations
• Robust combinatorial optimization under convex and discrete cost uncertainty
• Robust recoverable 0-1 optimization problems under polyhedral uncertainty

This page was built for publication: The recoverable robust spanning tree problem with interval costs is polynomially solvable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2361123)