Complexity and in-approximability of a selection problem in robust optimization

DOI10.1007/s10288-012-0227-7zbMath1287.90085MaRDI 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

zbMATH Keywords

computational complexity; combinatorial optimization; robust optimization; NP-hardness; inapproximability

Mathematics Subject Classification ID

62F35: Robustness and adaptive procedures (parametric inference)

90C47: Minimax problems in mathematical programming

90C27: Combinatorial optimization

90C39: Dynamic programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Robust approach to restricted items selection problem, Approximability of the robust representatives selection problem, Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, Recoverable robust representatives selection problems with discrete budgeted uncertainty, Robust combinatorial optimization with locally budgeted uncertainty, Two-stage combinatorial optimization problems under risk, Combinatorial optimization problems with balanced regret

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 \)