On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

DOI10.1016/j.orl.2006.09.007zbMath1149.90393OpenAlexW1988146710MaRDI QIDQ2457271

Paweł Zieliński, Adam Kasperski

Publication date: 30 October 2007

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

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

zbMATH Keywords

combinatorial optimizationFPTASMinmax regret

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27)

Related Items (10)

A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ Universal Algorithms for Clustering Problems ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ On the approximability of minmax (regret) network optimization problems ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey

Cites Work

• A branch and bound algorithm for the robust spanning tree problem with interval data
• Complexity of the min-max and min-max regret assignment problems
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• A branch and bound algorithm for the robust shortest path problem with interval data.
• Interval data minmax regret network optimization problems
• The robust shortest path problem in series -- parallel multidigraphs with interval data
• The Recognition of Series Parallel Digraphs
• The robust spanning tree problem with interval data

This page was built for publication: On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data