Approximating multiobjective knapsack problems

• 成果类型: Article
• 署名作者: Erlebach, T; Kellerer, H; Pferschy, U
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Graz
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.48.12.1603.445
• 发表日期: 2002
• 页码: 1603-1612
• 关键词: knapsack problem; multiobjective optimization; approximation scheme

摘要

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.