haku: @indexterm Knapsack problem / yhteensä: 30
viite: 1 / 30
« edellinen | seuraava »
Tekijä: | Erlebach, T. Kellerer, H. Pferschy, U. |
Otsikko: | Approximating multiobjective knapsack problems |
Lehti: | Management Science
2002 : DEC, VOL. 48:12, p. 1603-1612 |
Asiasana: | Knapsack problem Optimization |
Vapaa asiasana: | Approximation scheme |
Kieli: | eng |
Tiivistelmä: | For the multiobjective one-dimensional knapsack problem, a practical fully polynomial-time approximation scheme (FPTAS) is derived in this study. It is based on a new approach to the single-objective knapsack problem using a partition of the profit space into intervals of exponentially increasing length. For the multiobjective m-dimensional knapsack problem, the first known polynomial-time approximation scheme (PTAS), based on a linear programming, is presented. |
« edellinen | seuraava »
SCIMA