Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142285 | Operations Research Letters | 2015 | 6 Pages |
Abstract
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 ε 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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Cristina Bazgan, Florian Jamain, Daniel Vanderpooten,