Some tractable instances of interval data minmax regret problems

DOI10.1016/j.orl.2007.12.004zbMath1155.90467OpenAlexW2046158724MaRDI QIDQ1003488

Olivier Spanjaard, Bruno Escoffier, Jérôme Monnot

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.orl.2007.12.004

zbMATH Keywords

shortest pathspanning treerobust optimizationinterval databipartite perfect matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (2)

On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

Cites Work

• Unnamed Item
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Non deterministic polynomial optimization problems and their approximations
• Robust discrete optimization and its applications
• On the complexity of the robust spanning tree problem with interval data
• Interval data minmax regret network optimization problems
• Dioïds and semirings: Links to fuzzy sets and other applications
• On digraph coloring problems and treewidth duality
• Contribution to nonserial dynamic programming
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• Optimal Reduction of Two-Terminal Directed Acyclic Graphs
• Parameterized and Exact Computation
• Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data

This page was built for publication: Some tractable instances of interval data minmax regret problems