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

DOI10.1051/RO/2023034zbMATH Open1519.90254arXiv2002.11830MaRDI QIDQ6041242FDOQ6041242

Authors: Nicolas Dupin 

Publication date: 26 May 2023

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Abstract: In this paper, p-dispersion problems are studied to select $pgeqslant2$ 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(pnlogn)$ time and $O(n)$ memory space. Max-Sum-Neighbor p-dispersion is proven solvable in $O(p{n}^2)$ time and{$O(n)$} space. Max-Sum-min p-dispersion is solvable in $O(p{n}^3)$ time and $O(p{n}^2)$ space, this complexity holds 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 a practical application inside bi-objective meta-heuristics.

Full work available at URL: https://arxiv.org/abs/2002.11830

Recommendations

• Heuristic and Special Case Algorithms for Dispersion Problems
• scientific article; zbMATH DE number 1182762
• A comparison of \(p\)-dispersion heuristics
• The discrete p-dispersion problem
• Exact algorithms for the max-min dispersion problem

zbMATH Keywords

optimizationalgorithmsdynamic programmingcomplexitybi-objective optimizationPareto front\(p\)-dispersionskyline operator

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Dynamic programming (90C39) Discrete location and assignment (90B80)

Cited In (2)

• Polynomial algorithm for finding an asymptotically optimal solution to the multi-index planar choice problem.
• Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

This page was built for publication: Polynomial algorithms for p-dispersion problems in a planar Pareto Front

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041242)