A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

DOI10.1016/j.orl.2010.03.002zbMath1197.90337OpenAlexW2001532848MaRDI QIDQ991475

Eduardo Conde

Publication date: 7 September 2010

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

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

zbMATH Keywords

minmax regretrobust optimizationapproximation algorithms

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (10)

Heuristic algorithms for the minmax regret flow-shop problem with interval processing times ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Minmax regret combinatorial optimization problems with investments ⋮ The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ A single-machine scheduling problem with uncertainty in processing times and outsourcing costs ⋮ A minmax regret version of the time-dependent shortest path problem

Cites Work

• The computational complexity of the relative robust shortest path problem with interval data
• A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• A heuristic to minimax absolute regret for linear programs with interval objective function coefficients
• On the complexity of minmax regret linear programming
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• State Constraints in Convex Control Problems of Bolza

This page was built for publication: A 2-approximation for minmax regret problems via a mid-point scenario optimal solution