A new fully polynomial time approximation scheme for the knapsack problem

被引：67

作者：

Kellerer, H ^{[1
]}

Pferschy, U ^{[1
]}

机构：

[1] Graz Univ, Dept Stat & Operat Res, A-8010 Graz, Austria

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 1999年 / 3卷 / 01期

关键词：

knapsack problem; fully polynomial approximation scheme;

D O I：

10.1023/A:1009813105532

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/epsilon(3)) and O(n . 1/epsilon) space, respectively. Our new approximation scheme requires only O(n + 1/epsilon(2)) space while also reducing the running time.

引用

页码：59 / 71

页数：13