On the complexity of the robust spanning tree problem with interval data

DOI10.1016/S0167-6377(03)00058-0zbMATH Open1056.90114MaRDI QIDQ1433657FDOQ1433657

Authors: Ionuţ D. Aron, Pascal Van Hentenryck 

Publication date: 1 July 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Recommendations

• The computational complexity of the relative robust shortest path problem with interval data
• The robust spanning tree problem with interval data
• Recoverable robust spanning tree problem under interval uncertainty representations
• The robust fractional spanning tree problem with interval data
• A branch and bound algorithm for the robust spanning tree problem with interval data

zbMATH Keywords

UncertaintyInterval dataRobust optimizationRobust spanning tree

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Robust discrete optimization and its applications
• The robust spanning tree problem with interval data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On trees of a graph and their generation

Cited In (37)

• Euclidean minimum spanning trees with independent and dependent geometric uncertainties
• The robust minimum spanning tree problem: compact and convex uncertainty
• Risk models for the prize collecting Steiner tree problems with interval data
• Title not available (Why is that?)
• Choosing robust solutions in discrete optimization problems with fuzzy costs
• A polynomial solvable minimum risk spanning tree problem with interval data
• A relaxation algorithm with a probabilistic guarantee for robust deviation optimization
• Heuristics for the central tree problem
• Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
• Approximate robust optimization for the connected facility location problem
• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• Simulated annealing algorithm for the robust spanning tree problem
• On the enumeration of non-dominated spanning trees with imprecise weights
• Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
• The balanced minimum evolution problem under uncertain data
• Robust inference of trees
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• The minimum spanning tree problem with fuzzy costs
• Restricted robust uniform matroid maximization under interval uncertainty
• Improved polynomial algorithms for robust bottleneck problems with interval data
• On the approximability of robust spanning tree problems
• Recoverable robust spanning tree problem under interval uncertainty representations
• The update complexity of selection and related problems
• On the approximability of minmax (regret) network optimization problems
• Some tractable instances of interval data minmax regret problems
• Deterministic risk control for cost-effective network connections
• Complexity of the min-max and min-max regret assignment problems
• On exact solutions for the minmax regret spanning tree problem
• Complexity of the min-max (regret) versions of min cut problems
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Query minimization under stochastic uncertainty
• On the enumeration of non-dominated matroids with imprecise weights
• A branch and bound algorithm for the robust spanning tree problem with interval data
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• Optimal path discovery problem with homogeneous knowledge
• Robust discrete spanning tree problem: local search algorithms
• Combinatorial two-stage minmax regret problems under interval uncertainty

This page was built for publication: On the complexity of the robust spanning tree problem with interval data

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