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

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

zbMATH Keywords

computational complexitycombinatorial optimizationrobust optimizationNP-hardnessinapproximability

Mathematics Subject Classification ID

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