A fully polynomial approximation algorithm for the 0–1 knapsack problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Nov 1981 English Publisher:Elsevier BVJournal:European Journal of Operational Research, volume 8, pages 270-273 (issn: 0377-2217,

Copyright policy )

Authors: Magazine, M. J.; Oguz, Osman;

doi: 10.1016/0377-2217(81)90175-2

A fully polynomial approximation algorithm for the 0–1 knapsack problem

- Summary
- Subjects
- Metrics

Abstract

Abstract A fully polynomial ϵ-approximation algorithm is developed for the 0–1 knapsack problem. The algorithm uses results of Lawler and Ibarra and Kim. A pseudo-polynomial dynamic programming algorithm is first suggested which solves the problem in O( nb log n ) time and O( b ) space.

Related Organizations

University of Waterloo
Canada
Middle East Technical University
Turkey

Keywords

Numerical mathematical programming methods, Analysis of algorithms and problem complexity, Boolean programming, NP- complete problem, Dynamic programming, polynomial epsilon-approximation algorithm, 0-1 knapsack problem

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	50
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average