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

DOI10.1016/J.ORL.2010.03.002MaRDI QIDQ991475zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsrobust optimizationminmax regret

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(11)

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

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)