Some tractable instances of interval data minmax regret problems

DOI10.1016/J.ORL.2007.12.004MaRDI QIDQ1003488zbMATH OpenOpenAlexFDO

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

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

robust optimizationshortest pathinterval dataspanning treebipartite perfect matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Interval data minmax regret network optimization problems
• On a Class of Interval Data Minmax Regret CO Problems
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

Cites work

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

Cited in

(6)

• Algorithms for the minmax regret path problem with interval data
• Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• On a Class of Interval Data Minmax Regret CO Problems
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• Complexity of minimizing the total flow time with interval data and minmax regret criterion

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

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