Abstract | ||
---|---|---|
In the present work, we are interested in the practical behavior of a new fptas to solve the approximation version of the 0-1 multiobjective 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. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-75520-3_63 | ESA |
Keywords | Field | DocType |
multi-objective knapsack problem,general technique,extensive numerical experiment,dominance relation,exact method,cpu time,practical efficient fptas,approximation version,practical behavior,dynamic programming,good practical performance,new fptas,approximation,combinatorial optimization,knapsack problem | Dynamic programming,Mathematical optimization,Combinatorics,Computer science,Change-making problem,CPU time,Continuous knapsack problem,Combinatorial optimization,Cutting stock problem,Knapsack problem | Conference |
Volume | ISSN | ISBN |
4698 | 0302-9743 | 3-540-75519-5 |
Citations | PageRank | References |
2 | 0.42 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cristina Bazgan | 1 | 679 | 62.76 |
Hadrien Hugot | 2 | 47 | 3.25 |
Daniel Vanderpooten | 3 | 1153 | 74.66 |