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

DOI10.1016/J.ORL.2006.09.007MaRDI QIDQ2457271zbMATH OpenOpenAlexFDO

Authors Adam Kasperski, Paweł Zieliński

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

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

Recommendations

• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• Computing and minimizing the relative regret in combinatorial optimization with interval data
• On a Class of Interval Data Minmax Regret CO Problems

Cites work

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

Cited in

(16)

• Some tractable instances of interval data minmax regret problems
• 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
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• Algorithms for the minmax regret path problem with interval data
• Combinatorial two-stage minmax regret problems under interval uncertainty
• Approximating Single Machine Scheduling with Scenarios
• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• 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
• Robust algorithms for TSP and Steiner tree
• Universal algorithms for clustering problems
• On the approximability of minmax (regret) network optimization problems

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

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