Pinpointing the complexity of the interval min-max regret knapsack problem

DOI10.1016/j.disopt.2010.03.008zbMath1241.90178OpenAlexW2094834697MaRDI QIDQ429656

Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 20 June 2012

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

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

zbMATH Keywords

computational complexityrobust optimizationpolynomial hierarchy

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (11)

An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Robust min-max regret covering problems ⋮ Combinatorial optimization problems with balanced regret ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ On the complexity of robust multi-stage problems with discrete recourse ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times ⋮ The trouble with the second quantifier

Cites Work

• Unnamed Item
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• The polynomial-time hierarchy
• Robust discrete optimization and its applications
• The robust spanning tree problem with interval data

This page was built for publication: Pinpointing the complexity of the interval min-max regret knapsack problem