Approximate Pareto sets of minimal size for multi-objective optimization problems

摘要

We are interested in a problem introduced by Vassilvitskii and Yannakakis (2005), the computation of a minimum set of solutions that approximates within an accuracy epsilon the Pareto set of a multi-objective optimization problem. We mainly establish a new 3-approximation algorithm for the bi-objective case. We also propose a study of the greedy algorithm performance for the tri-objective case when the points are given explicitly, answering an open question raised by Koltun and Papadimitriou in (2007). (C) 2014 Elsevier B.V. All rights reserved.