The Linear Multiple Choice Knapsack Problem

Eitan Zemel
Additional contact information
Eitan Zemel: Northwestern University, Evanston, Illinois

Operations Research, 1980, vol. 28, issue 6, 1412-1423

Abstract: A fast algorithm is presented for the linear programming relaxation of the Multiple Choice Knapsack Problem. If N is the total number of variables and J and J max denote the total number of multiple choice variables and the cardinality of the largest multiple choice set, respectively, the running time of the algorithm is then bounded by 0( J log J max ) + 0( N ). Under certain conditions it is possible to reduce this bound to 0( N ) steps on the average. Possible further improvements are also discussed.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.6.1412 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:28:y:1980:i:6:p:1412-1423

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().