Approximating Multiobjective Knapsack Problems

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...

Full description

Saved in:
Bibliographic Details
Published in:Management science 2002-12, Vol.48 (12), p.1603-1612
Main Authors: Erlebach, Thomas, Kellerer, Hans, Pferschy, Ulrich
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
approximation scheme
Bibliographic literature
Business studies
Combinatorial optimization
Computer programmes
Computer science
Discounts
Dynamic programming
Error rates
Genetic algorithms
Knapsack problem
Linear programming
Mail order
Management science
Mathematical intervals
multiobjective optimization
Objective functions
Operations research
Optimal solutions
Optimization
Optimization algorithms
Polynomials
Profits
Statistical analysis
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.48.12.1603.445