Solving sequential knapsack problems

Solving sequential knapsack problems

0.00 Avg rating—0 Votes
Article ID: iaor1995324
Country: Netherlands
Volume: 13
Issue: 4
Start Page Number: 225
End Page Number: 232
Publication Date: May 1993
Journal: Operations Research Letters
Authors: ,
Keywords: knapsack problem
Abstract:

The authors give an O(nlogn) algorithm for solving sequential knapsack problems, whose bottleneck operation is sorting the ratios cj/aj; otherwise the running time is O(n). This is used to compute a better bound than zLP for the general 0-1 knapsack problem in linear time after sorting the ratios cj/aj.

Reviews

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