A Linked List Data Structure for a Binary Knapsack Algorithm.

Abstract

This paper describes a novel application for a linked list in Greenberg's and Hegerich's 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.

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1975
Accession Number
ADA017934

Entities

People

  • G. Terry Ross
  • Richard S. Barr

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Digital Information
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Lists (Data Structures)
  • Mathematics
  • Simplex Method

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Library and Information Science/ Studies, Southeast Asia Studies, Bibliography of Vietnam and Lao Studies.
  • Theoretical Analysis.