|
Authors: | Thomas Erlebach, Hans Kellerer, Ulrich Pferschy |
Group: | Theory of Communication Networks |
Type: | Article |
Title: | Approximating Multiobjective Knapsack Problems |
Year: | 2002 |
Month: | December |
Pub-Key: | EKP02ms |
Journal: | Management Science |
Volume: | 48 |
Number: | 12 |
Pages: | 1603-1612 |
Abstract: | For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in which each item has several profit values. For this problem, efficient algorithms for computing a provably good approximation to the set of all nondominated feasible solutions, the Pareto frontier, are studied. For the multiobjective one-dimensional knapsack problem, a practical fully polynomial time approximation scheme (FPTAS) is derived. It is based on a new approach to the singleobjective 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 linear programming, is presented. |
Resources: | [BibTeX] |