On the complexity of the robust spanning tree problem with interval data
From MaRDI portal
Publication:1433657
DOI10.1016/S0167-6377(03)00058-0zbMath1056.90114MaRDI QIDQ1433657
Pascal Van Hentenryck, Ionuţ D. Aron
Publication date: 1 July 2004
Published in: Operations Research Letters (Search for Journal in Brave)
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (32)
Robust inference of trees ⋮ Approximate robust optimization for the connected facility location problem ⋮ The update complexity of selection and related problems ⋮ The robust minimum spanning tree problem: compact and convex uncertainty ⋮ On exact solutions for the minmax regret spanning tree problem ⋮ Restricted robust uniform matroid maximization under interval uncertainty ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ Deterministic risk control for cost-effective network connections ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ The balanced minimum evolution problem under uncertain data ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ Simulated annealing algorithm for the robust spanning tree problem ⋮ Euclidean minimum spanning trees with independent and dependent geometric uncertainties ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ On the approximability of minmax (regret) network optimization problems ⋮ A branch and bound algorithm for the robust spanning tree problem with interval data ⋮ Heuristics for the central tree problem ⋮ A relaxation algorithm with a probabilistic guarantee for robust deviation optimization ⋮ Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality ⋮ Some tractable instances of interval data minmax regret problems ⋮ Query minimization under stochastic uncertainty ⋮ Optimal path discovery problem with homogeneous knowledge ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ Computing and minimizing the relative regret in combinatorial optimization with interval data ⋮ A polynomial solvable minimum risk spanning tree problem with interval data ⋮ The minimum spanning tree problem with fuzzy costs ⋮ Choosing robust solutions in discrete optimization problems with fuzzy costs ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights ⋮ An approximation algorithm for interval data minmax regret combinatorial optimization problems ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ Robust discrete spanning tree problem: local search algorithms ⋮ Complexity of the min-max and min-max regret assignment problems
Cites Work
This page was built for publication: On the complexity of the robust spanning tree problem with interval data
