When the Greedy Solution Solves a Class of Knapsack Problems.

Abstract

A heuristic for the knapsack problem that recursively determines a solution by making a variable with smallest marginal cost as large as possible is studied. Recursive necessary and sufficient conditions for the optimality of such greedy solutions and a good algorithm for verifying these conditions are given. Maximum absolute error for non-optimal greedy solutions is also examined. (Author)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1974
Accession Number
AD0779438

Entities

People

  • G. L. Nemhauser
  • L. E. Trotter Jr.
  • M. J. Magazine

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Continents
  • Cooperation
  • Geographic Regions
  • Group Dynamics
  • Mathematics
  • North America
  • North Carolina

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.