DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA017934
Title:
A Linked List Data Structure for a Binary Knapsack Algorithm.
Descriptive Note:
Research rept.,
Corporate Author:
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Report Date:
1975-08-01
Pagination or Media Count:
30.0
Abstract:
This paper describes a novel application for a linked list in Greenbergs and Hegerichs algorithm for the binary knapsack problem. This list accelerates the solution of the problem by providing an efficient method for solving linear programming relaxations of the problem. Computational testing on 400 randomly generated problems with up to 7,500 variables is reported. For these problems, average solution times increase linearly with problem size when the linked list is used. The effectiveness of various problem reduction schemes is also explored.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
