Polynomial algorithms for p-dispersion problems in a 2d Pareto Front

02/26/2020
by   Nicolas Dupin, et al.
0

Having many best compromise solutions for bi-objective optimization problems, this paper studies p-dispersion problems to select p⩾ 2 representative points in the Pareto Front(PF). Four standard variants of p-dispersion are considered. A novel variant, denoted Max-Sum-Neighbor p-dispersion, is introduced for the specific case of a 2d PF. Firstly, it is proven that 2-dispersion and 3-dispersion problems are solvable in O(n) time in a 2d PF. Secondly, dynamic programming algorithms are designed for three p-dispersion variants, proving polynomial complexities in a 2d PF. The Max-Min p-dispersion problem is proven solvable in O(pnlog n) time and O(n) memory space. The Max-Sum-Min p-dispersion problem is proven solvable in O(pn^3) time and O(pn^2) space. The Max-Sum-Neighbor p-dispersion problem is proven solvable in O(pn^2) time and O(pn) space. Complexity results and parallelization issues are discussed in regards to practical implementation.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset