search query: @author Kellerer, H. / total: 2
reference: 2 / 2
« previous | next »
| Author: | Erlebach, T. Kellerer, H. Pferschy, U. |
| Title: | Approximating multiobjective knapsack problems |
| Journal: | Management Science
2002 : DEC, VOL. 48:12, p. 1603-1612 |
| Index terms: | Knapsack problem Optimization |
| Freeterms: | Approximation scheme |
| Language: | eng |
| Abstract: | 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. |
« previous | next »
SCIMA