Northwestern Kellogg logo

Take Action

Home | Faculty & Research Overview | Research

Research Details

A Computational Study of a Multiple-Choice Knapsack Algorithm, ACM Transactions on Mathematical Software

Abstract

The results from the computational testing of an algorithm designed to solve large-scale multiple-choice knapsack problems are described. Data list structures, sorting techniques, and fathoming criteria are investigated. It is determined that considerable storage space can be eliminated from the original implementation of the algorithm without affecting execution time. Also the insertion of a heap sort in the algorithm does provide a substantial reduction in computing time when solving the larger problems. Theoretical results relating to the multiple-choice knapsack are presented.

Type

Article

Author(s)

Ronald D Armstrong, D. S. Kung, Prabhakant Sinha, Andris Zoltners

Date Published

1983

Citations

Armstrong, Ronald D, D. S. Kung, Prabhakant Sinha, and Andris Zoltners. 1983. A Computational Study of a Multiple-Choice Knapsack Algorithm. ACM Transactions on Mathematical Software.(2)

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more