On the complexity of minmax regret linear programming

DOI10.1016/j.ejor.2003.07.007zbMath1067.90132OpenAlexW2089510325MaRDI QIDQ1887882

Igor Averbakh, Vasilij N. Lebedev

Publication date: 22 November 2004

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2003.07.007

zbMATH Keywords

Combinatorial optimizationUncertainty modelingComplexity theoryMinmax regret optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Complexity and performance of numerical algorithms (65Y20)

Related Items

Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Regret minimization, willingness-to-accept-losses and framing ⋮ Robust optimal solutions in interval linear programming with forall-exists quantifiers ⋮ An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives ⋮ Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ Minmax regret linear resource allocation problems. ⋮ Constraint-based optimization and utility elicitation using the minimax decision criterion ⋮ Robust combinatorial optimization under convex and discrete cost uncertainty ⋮ Violation analysis on two-step method for interval linear programming ⋮ Linear programming with interval right hand sides ⋮ On the approximability of minmax (regret) network optimization problems ⋮ A 2-approximation for minmax regret problems via a mid-point scenario optimal solution ⋮ Maximum excess dominance: identifying impractical solutions in linear problems with interval coefficients ⋮ Pessimistic, optimistic, and minimax regret approaches for linear programs under uncertainty ⋮ Best and Worst Optimum for Linear Programs with Interval Right Hand Sides ⋮ Robust Postdonation Blood Screening Under Prevalence Rate Uncertainty ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ Robustness in operational research and decision aiding: a multi-faceted issue ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Minimax regret solution to linear programming problems with an interval objective function
• A heuristic to minimax absolute regret for linear programs with interval objective function coefficients
• A possibilistic linear program is equivalent to a stochastic linear program in a special case
• The complexity of satisfiability problems
• On the complexity of a class of combinatorial optimization problems with uncertainty