A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem |
| |
| Authors: | Hans Kellerer Ulrich Pferschy |
| |
| Institution: | (1) Department of Statistics and Operations Research, University of Graz, Universitätsstr. 15, A-8010 Graz, Austria |
| |
| Abstract: | 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/ 3) and O(n · 1/) space, respectively. Our new approximation scheme requires only O(n + 1/2) space while also reducing the running time. |
| |
| Keywords: | knapsack problem fully polynomial approximation scheme |
| 本文献已被 SpringerLink 等数据库收录！ |
