On the complexity of minmax regret linear programming

DOI10.1016/j.ejor.2003.07.007zbMath1067.90132MaRDI 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 optimization; Uncertainty modeling; Complexity theory; Minmax regret optimization

Mathematics Subject Classification ID

90C27: Combinatorial optimization

65Y20: Complexity and performance of numerical algorithms

Related Items

Regret minimization, willingness-to-accept-losses and framing, On the approximability of minmax (regret) network optimization problems, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution, 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, Minmax regret linear resource allocation problems., Constraint-based optimization and utility elicitation using the minimax decision criterion, Linear programming with interval right hand sides, Best and Worst Optimum for Linear Programs with Interval Right Hand Sides

Cites Work

• 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
• Unnamed Item
• Unnamed Item