An O(n3) worst case bounded special LP knapsack (0-1) with two constraints

An O(n3) worst case bounded special LP knapsack (0-1) with two constraints

0.00 Avg rating—0 Votes
Article ID: iaor19891007
Country: France
Volume: 22
Issue: 1
Start Page Number: 27
End Page Number: 32
Publication Date: Feb 1988
Journal: RAIRO Operations Research
Authors: ,
Keywords: knapsack problem
Abstract:

In this paper it is shown that a linear knapsack 0-1 problem amended with a nontrivial multiple-choice constraint can be solved by an algorithm requiring running time O(n3). Though not being a new result the approach of the proof is worth reporting for it is based on the nice ideas of geometric complexity and efficient median-finding.

Reviews

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