Complexity Results and Exact Algorithms for Robust Knapsack Problems

Complexity Results and Exact Algorithms for Robust Knapsack Problems

0.00 Avg rating0 Votes
Article ID: iaor2014739
Volume: 161
Issue: 2
Start Page Number: 533
End Page Number: 552
Publication Date: May 2014
Journal: Journal of Optimization Theory and Applications
Authors: ,
Keywords: complexity, knapsack problem
Abstract:

This paper studies the robust knapsack problem, for which solutions are, up to a certain point, immune from data uncertainty. We complement the works found in the literature, where uncertainty affects only the profits or only the weights of the items, by studying the complexity and approximation of the general setting with uncertainty regarding both the profits and the weights, for three different objective functions. Furthermore, we develop a scenario‐relaxation algorithm for solving the general problem and present computational results.

Reviews

Required fields are marked *. Your email address will not be published.