论文标题
Planar Pareto前部P分散问题的多项式算法
Polynomial algorithms for p-dispersion problems in a planar Pareto Front
论文作者
论文摘要
在本文中，研究了p分散问题，以从大型2D Pareto Front（PF）（BI-Obigntive优化解决方案）中选择$ P \ geqslant 2 $代表点。考虑了四个标准的P分散变体。针对2D PF的特定情况，引入了一种新型的变体，最大 - 邻居P分散。首先，$ 2 $ - 分散和$ 3 $ - 分散问题可在2D PF中以$ o（n）$时间的速度解决。其次，动态编程算法是为三个P分散变体设计的，在2D PF中证明了多项式复杂性。 Max-min p-dispersion可在$ O（pn \ log n）$ time和$ o（n）$内存空间中解决。 Max-sum-neighbor p-dispersion可在$ O（pn^2）$ time和{$ o（n）$} space中溶解。 Max-sum-min p分散可在$ o（pn^3）$ time和$ o（pn^2）$ space中溶解，这种复杂性也保持在1D中，这首先证明了Max-sum-sum-min p-dispersion在1D中是多项式的。此外，讨论了这些算法的属性，以进行有效的实现（以及在双目标元元术中的实际应用。
In this paper, p-dispersion problems are studied to select $p\geqslant 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^2)$ time and{$O(n)$} space. Max-Sum-min p-dispersion is solvable in $O(pn^3)$ time and $O(pn^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.
