On the complexity of the continuous unbounded knapsack problem with uncertain coefficients

On the complexity of the continuous unbounded knapsack problem with uncertain coefficients

0.00 Avg rating0 Votes
Article ID: iaor2006337
Country: Netherlands
Volume: 33
Issue: 5
Start Page Number: 481
End Page Number: 485
Publication Date: Sep 2005
Journal: Operations Research Letters
Authors:
Keywords: knapsack problem
Abstract:

In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of O(n log(n)) time for this optimization problem.

Reviews

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