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

DOI10.1016/J.DISOPT.2010.03.008MaRDI QIDQ429656zbMATH OpenOpenAlexFDO

Authors Gerhard J. Woeginger, Vladimir G. Deineko

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

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

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Robust discrete optimization and its applications
• The polynomial-time hierarchy
• The robust spanning tree problem with interval data

Cited in

(13)

• On the complexity of robust multi-stage problems with discrete recourse
• The trouble with the second quantifier
• Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
• Combinatorial optimization problems with balanced regret
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
• Robust min-max regret covering problems
• scientific article; zbMATH DE number 7368387 (Why is no real title available?)
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429656)