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

DOI10.1016/J.ORL.2010.03.002zbMATH Open1197.90337OpenAlexW2001532848MaRDI QIDQ991475FDOQ991475

Authors: E. 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

Recommendations

• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem

zbMATH Keywords

approximation algorithmsrobust optimizationminmax regret

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines
• A minmax regret version of the time-dependent shortest path problem
• Minmax regret combinatorial optimization problems with investments
• Heuristic algorithms for the minmax regret flow-shop problem with interval processing times
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
• 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
• Combinatorial two-stage minmax regret problems under interval uncertainty

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

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