Complexity and in-approximability of a selection problem in robust optimization
From MaRDI portal
Publication:385465
DOI10.1007/s10288-012-0227-7zbMath1287.90085OpenAlexW2029243025MaRDI QIDQ385465
Gerhard J. Woeginger, Vladimir G. Deǐneko
Publication date: 2 December 2013
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-012-0227-7
Robustness and adaptive procedures (parametric inference) (62F35) Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, Robust approach to restricted items selection problem, Recoverable robust representatives selection problems with discrete budgeted uncertainty, Robust combinatorial optimization with locally budgeted uncertainty, Combinatorial optimization problems with balanced regret, Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints, Approximability of the robust representatives selection problem, Two-stage combinatorial optimization problems under risk
Cites Work
- Unnamed Item
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Robust discrete optimization and its applications
- Min-max and min-max (relative) regret approaches to representatives selection problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)