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

DOI10.1016/J.DISOPT.2010.03.008zbMATH Open1241.90178OpenAlexW2094834697MaRDI QIDQ429656FDOQ429656

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

• Title not available (Why is that?)
• Robust discrete optimization and its applications
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• The robust spanning tree problem with interval data
• The polynomial-time hierarchy

Cited In (13)

• Title not available (Why is that?)
• Robust min-max regret covering problems
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• 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
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• The trouble with the second quantifier
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times
• Combinatorial optimization problems with balanced regret
• An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem

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)