Complexity of min-max-min robustness for combinatorial optimization under discrete uncertainty

DOI10.1016/j.disopt.2017.08.006zbMath1474.90371OpenAlexW2767276898MaRDI QIDQ1662157

Jannis Kurtz, Christoph Buchheim

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2017.08.006

zbMATH Keywords

robust optimization\(k\)-adaptabilitydiscrete uncertainty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

The min-p robust optimization approach for facility location problem under uncertainty, Min-Max-Min Optimization with Smooth and Strongly Convex Objectives, Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions, \(K\)-adaptability in two-stage mixed-integer robust optimization, Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty, \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty, Oracle-based algorithms for binary two-stage robust optimization, Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty

Cites Work

• Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions
• Min-max-min robust combinatorial optimization
• Complexity of the min-max and min-max regret assignment problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Robust solutions of uncertain linear programs
• Adjustable robust solutions of uncertain linear programs
• Multicriteria global minimum cuts
• Robust Convex Optimization
• Lagrangean Decomposition for Mean-Variance Combinatorial Optimization
• K-Adaptability in Two-Stage Robust Binary Programming
• The Price of Robustness
• Robust Solutions to Uncertain Semidefinite Programs
• Robust Solutions to Least-Squares Problems with Uncertain Data
• Finite Adaptability in Multistage Linear Optimization
• Algorithms – ESA 2005
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• Algorithms and Computation