Approximating Multiobjective Knapsack Problems

Thomas Erlebach (), Hans Kellerer () and Ulrich Pferschy ()
Additional contact information
Thomas Erlebach: Computer Engineering and Networks Laboratory, ETH Zürich, CH-8092 Zürich, Switzerland
Hans Kellerer: University of Graz, Department of Statistics and Operations Research, Universitätsstr. 15, A-8010 Graz, Austria
Ulrich Pferschy: University of Graz, Department of Statistics and Operations Research, Universitätsstr. 15, A-8010 Graz, Austria

Management Science, 2002, vol. 48, issue 12, 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 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 linear programming, is presented.

Keywords: knapsack problem; multiobjective optimization; approximation scheme (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.48.12.1603.445 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:48:y:2002:i:12:p:1603-1612

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().