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

DOI10.1007/s11590-016-1057-xzbMath1373.90086arXiv1602.07422OpenAlexW2469064012WikidataQ59609887 ScholiaQ59609887MaRDI QIDQ2361123

Paweł Zieliński, Adam Kasperski, Mikita Hradovich

Publication date: 29 June 2017

Published in: Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

spanning treematroidsrobust optimizationinterval data

Mathematics Subject Classification ID

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

Related Items

Investigating the recoverable robust single machine scheduling problem under interval uncertainty ⋮ Matroid bases with cardinality constraints on the intersection ⋮ Recoverable robust representatives selection problems with discrete budgeted uncertainty ⋮ Recoverable robust spanning tree problem under interval uncertainty representations ⋮ On recoverable and two-stage robust selection problems with budgeted uncertainty ⋮ Robust recoverable 0-1 optimization problems under polyhedral uncertainty ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ A linear time algorithm for the robust recoverable selection problem ⋮ Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the recoverable robust traveling salesman problem
• On the approximability of robust spanning tree problems
• Recoverable robust knapsacks: the discrete scenario case
• Testing membership in matroid polyhedra
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Recoverable robust shortest path problems
• Iterative Methods in Combinatorial Optimization
• Incremental Network Optimization: Theory and Algorithms
• The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications
• Recoverable Robust Combinatorial Optimization Problems
• Matroids and the greedy algorithm

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