Polynomial algorithms for p-dispersion problems in a planar Pareto Front

Univ Angers, LERIA, SFR MATHSTIC, F-49000 Angers, France

^* Corresponding author: nicolas.dupin@univ-angers.fr

Received: 24 September 2021
Accepted: 22 March 2023

Abstract

In this paper, p-dispersion problems are studied to select p ⩾ 2 representative points from a large 2D Pareto Front (PF), solution of bi-objective optimization. Four standard p-dispersion variants are considered. A novel variant, Max-Sum-Neighbor p-dispersion, is introduced for the specific case of a 2D PF. Firstly, 2-dispersion and 3-dispersion problems are proven 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. Max-min p-dispersion is solvable in O(pn log n) time and O(n) memory space. Max-Sum-Neighbor p-dispersion is proven solvable in O(pn²) time and O(n) space. Max-Sum-min p-dispersion is solvable in O(pn³) time and O(pn²) space. These complexity results hold also in 1D, proving for the first time that Max-Sum-min p-dispersion is polynomial in 1D. Furthermore, properties of these algorithms are discussed for an efficient implementation and for practical applications.