A practical efficient fptas for the 0-1 multi-objective knapsack problem
Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2007), A practical efficient fptas for the 0-1 multi-objective knapsack problem, in Welzl, Emo, Algorithms - ESA 2007 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, Springer : Berlin Heidelberg, p. 717-728
TypeCommunication / Conférence
Book titleAlgorithms - ESA 2007 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings
Book authorWelzl, Emo
MetadataShow full item record
Abstract (EN)In the present work, we are interested in the practical behavior of a new fptas to solve the approximation version of the 0-1 multi-objective knapsack problem. Nevertheless, our methodology focuses on very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well. Extensive numerical experiments on various types of instances establish that our method performs very well both in terms of CPU time and size of solved instances. We point out some reasons for the good practical performance of our algorithm. A comparison with an exact method is also performed.
Subjects / KeywordsMulti-objective knapsack problem; dynamic programming; combinatorial optimization; dominance relations; approximation
Showing items related by title and author.
Discrete representation of the non-dominated set for multi-objective optimization problems using kernels Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié