The Linear Multiple Choice Knapsack Problem.

Abstract

We discuss a fast algorithm for the linear programming relaxation of the Multiple Choice Knapsack Problem. Let N be the total number of variables in this problem and let J and J sub 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 sub 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1979
Accession Number
ADA069129

Entities

People

  • Eitan Zemel

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Coefficients
  • Computational Complexity
  • Computer Programming
  • Geometry
  • Information Processing
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • Operations Research
  • Schools
  • Simplex Method
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Operations Research