Implementing an efficient fptas for the 0-1 multi-objective knapsack problem

DOI10.1016/j.ejor.2008.07.047zbMath1163.90726OpenAlexW2000124998MaRDI QIDQ1027579

Cristina Bazgan, Hadrien Hugot, Daniel Vanderpooten

Publication date: 30 June 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.07.047

zbMATH Keywords

dynamic programmingcombinatorial optimizationapproximationdominance relationsmulti-objective knapsack problem

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (17)

Dynamic programming algorithms for the bi-objective integer knapsack problem ⋮ Compressed data structures for bi-objective \(\{0,1\}\)-knapsack problems ⋮ Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Exact and approximate determination of the Pareto front using minimal correction subsets ⋮ Single machine scheduling with assignable due dates to minimize maximum and total late work ⋮ Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0-1 knapsack problems ⋮ A new effective dynamic program for an investment optimization problem ⋮ Approximation schemes for the parametric knapsack problem ⋮ Covers and approximations in multiobjective optimization ⋮ Discrete representation of the non-dominated set for multi-objective optimization problems using kernels ⋮ The small world of efficient solutions: empirical evidence from the bi-objective \(\{0,1\}\)-knapsack problem ⋮ Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms ⋮ The multiobjective multidimensional knapsack problem: a survey and a new approach ⋮ A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving efficiently the 0-1 multi-objective knapsack problem
• Heuristic algorithms for the multiple knapsack problem
• Solving bicriteria 0--1 knapsack problems using a labeling algorithm.
• On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems.
• Approximating Multiobjective Knapsack Problems
• Discrete Dynamic Programming and Capital Allocation
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Multicriteria Optimization

This page was built for publication: Implementing an efficient fptas for the 0-1 multi-objective knapsack problem