|
Authors: | Thomas Erlebach, Hans Kellerer, Ulrich Pferschy |
Group: | Theory of Communication Networks |
Type: | Inproceedings |
Title: | Approximating Multi-Objective Knapsack Problems |
Year: | 2001 |
Month: | August |
Pub-Key: | EKP01 |
Book Titel: | Lecture Notes in Computer Science. Proceedings of the Seventh International Workshop on Algorithms and Data Structures (WADS 2001) |
Volume: | 2125 |
Pages: | 210-221 |
Publisher: | Springer-Verlag |
Abstract: | For multi-objective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multi-objective 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 non-dominated feasible solutions, the Pareto frontier, are studied. For the multi-objective 1-dimensional knapsack problem, a fast fully polynomial-time approximation scheme is derived. 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 multi-objective m-dimensional knapsack problem, the first known polynomial-time approximation scheme, based on linear programming, is presented. |
Location: | Providence, RI |
Resources: | [BibTeX] |