Papers › Polynomial algorithms for p-dispersion problems in a planar Pareto Front
Polynomial algorithms for p-dispersion problems in a planar Pareto Front
Nicolas Dupin
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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(pnlogn) 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, 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections