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

Nicolas Dupin

###### Abstract

Having many best compromise solutions for bi-objective optimization problems,
this paper studies p-dispersion problems to select $p\geqslant 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(pn\log 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.

Keywords : Optimization, Operational Research, Computational Geometry ;
Dynamic programming ; p-dispersion problems ; complexity ; bi-objective
optimization ; Pareto front ; Parallel Computing

##  1 Introduction

This paper is motivated by real-life applications of multi-objective
optimization (MOO) [5, 25]. Many best compromise solutions may exist
considering the Pareto dominance [11]. A Pareto Front (PF) denotes the
projection of these solutions in the space of the objectives. This work aims
to select $p$ solutions from $n\gg p$ non dominated solutions, while
maximizing the diversity of these $p$ solutions in the objective space.
Firstly, such problem occurs when selecting alternatives for decision makers,
$p$ is small in such applications. Secondly, a similar problem occurs inside
MOO meta-heuristics to archive diversified solutions of the PF, $p$ is larger
in such applications [32, 34]. For such problem, one can use the hypervolume
measure as in [2, 21], or clustering algorithms as studied in [6, 7, 8].

In this paper, we consider (discrete) p-dispersion problems, dispersing the
selected points as much as possible, as in [12]. Actually, four variants of
discrete p-dispersion problems are defined [13]. Max-Min and Max-Sum
p-dispersion problems, the most studied variants, are proven NP-complete in
the general case ([12, 16]). Although p-dispersion is mentioned to have
relevant applications for MOO [13, 27], no specific studies concerned the
p-dispersion in a PF to the best of our knowledge. This paper studies the four
variants of p-dispersion problems in the case of a 2-dimensional (2d) PF.
Another problem, denoted Max-Sum-Neighbor p-dispersion, is also introduced in
a 2d PF. For the five p-dispersion problems, the cases $p=2$ and $p=3$ are
proven to be solvable in $O(n)$ time. Generally, the Max-Min, Max-Sum-Min and
Max-Sum-Neighbor p-dispersion problems are proven to be solvable in polynomial
time in a 2d PF thanks to dynamic programming (DP) algorithms.

This paper is organized as following. In Section 2, we formally describe the
problem. In Section 3, we discuss related state-of-the-art elements to
appreciate our contributions. In Section 4, intermediate results are
presented, allowing to define the Max-Sum-Neighbor p-dispersion problem. In
Section 5, a DP algorithm is presented for the Max-Sum-Neighbor variant with a
complexity proven in $O(pn^{2})$ time and $O(pn)$ memory space. In section 6,
the previous DP algorithm is adapted for the Max-Min variant with a complexity
in $O(pn\log n)$ time and $O(n)$ space. In section 7, a DP algorithm is
presented for the Max-Min-Sum variant with a complexity in $O(pn^{3})$ time
and $O(pn^{2})$ space. In Section 8, practical applications are discussed. In
Section 9, our contributions are summarized, discussing also future directions
of research.

##  2 Problem statement and notation

We suppose in this paper having a set $E$ of $n$ elements of a 2d PF, where
the minimization of two objectives is considered (without loss of generality,
transforming objectives to maximize $f$ into $-f$). Similarly with [7], this
can be formalized $E=\\{x_{1},\dots,x_{n}\\}$, having $n$ elements of
${\mathbb{R}}^{2}$, such that for all $i\neq j$,
$x_{i}\phantom{0}\mathcal{I}\phantom{0}x_{j}$, defining the binary relations
$\mathcal{I},\prec$ for all
$y=(y^{1},y^{2}),z=(z^{1},z^{2})\in{\mathbb{R}}^{2}$ with:

$\displaystyle y\prec z$ $\displaystyle\Longleftrightarrow$ $\displaystyle
y^{1}<z^{1}\phantom{2}\mbox{and}\phantom{2}y^{2}>z^{2}$ (1) $\displaystyle
y\preccurlyeq z$ $\displaystyle\Longleftrightarrow$ $\displaystyle y\prec
z\phantom{2}\mbox{or}\phantom{2}y=z$ (2) $\displaystyle
y\phantom{1}\mathcal{I}\phantom{1}z$ $\displaystyle\Longleftrightarrow$
$\displaystyle y\prec z\phantom{2}\mbox{or}\phantom{2}z\prec y$ (3)

To measure distances between points $x_{i},x_{j}\in E$, we consider
$d_{ij}=d(x_{i},x_{j})^{\alpha}$ where $\alpha>0$ and $d$ is the Euclidian
distance:

$\forall
y=(y^{1},y^{2}),z=(z^{1},z^{2})\in{\mathbb{R}}^{2},\phantom{2}d(y,z)=\sqrt{\left(y^{1}-z^{1}\right)^{2}+\left(y^{2}-z^{2}\right)^{2}}$
(4)

The p-dispersion problems select $p\geqslant 2$ out of $n$ given candidate
points, while maximizing a dispersion function $f$:

${\mathcal{P}}_{disp}(E,p)=\max_{(z_{1},z_{2},\dots,z_{p})\in
D_{p}}f(z_{1},z_{2},\dots,z_{p})$ (5)

where $D_{p}$ denotes the set of all the distincts points of $E$:

$D_{p}=\\{(z_{1},z_{2},\dots,z_{p})\in E^{p}|\forall 1\leqslant i<j\leqslant
p,z_{i}\neq z_{j}\\}$ (6)

The most standard p-dispersion problem, also denoted Max-Min p-dispersion
problem or p-dispersion-MM, the dispersion function is the minimum of
distances $d_{ij}$ between pairs of the selected points. Formally, the Max-Min
p-dispersion problem for $p\geqslant 2$ can be written as:

${\mathcal{P}}_{disp}^{MM}(E,p)=\max_{(z_{1},z_{2},\dots,z_{p})\in
D_{p}}\min_{i,j:1\leqslant i<j\leqslant p}d_{ij}$ (7)

Another known variant is the Max-Sum(-Sum) dispersion problem, denoted
p-dispersion-MS, with:

${\mathcal{P}}_{disp}^{MS}(E,p)=\max_{(z_{1},z_{2},\dots,z_{p})\in
D_{p}}\sum_{i=1}^{p-1}\sum_{j=i+1}^{p}d_{ij}$ (8)

We consider also in this paper the Max-Sum-Min p-dispersion problem, denoted
p-dispersion-MSM:

${\mathcal{P}}_{disp}^{MSM}(E,p)=\max_{(z_{1},z_{2},\dots,z_{p})\in
D_{p}}\sum_{i=1}^{p}\min_{j\neq i:1\leqslant j\leqslant p}d_{ij}$ (9)

Another specific variant of Max-Sum-Min p-dispersion in a 2d PF will be
defined in the Section 4, using specific properties of a 2d PF. Lastly, the
Max-Min-Sum p-dispersion problem, denoted p-dispersion-MMS, is defined as
following:

${\mathcal{P}}_{disp}^{MMS}(E,p)=\max_{(z_{1},z_{2},\dots,z_{p})\in
D_{p}}\min_{i\in[\\![1,p]\\!]}\sum_{j\in[\\![1,p]\\!]-\\{i\\}}d_{ij}$ (10)

##  3 Related works

This section describes related works to appreciate the contributions of this
paper.

###  3.1 Complexity results for p-dispersion problems

Max-Min and Max-Sum p-dispersion problems are NP-hard problems[12, 16]. It is
proven in both cases by a polynomial reduction to the maximum independent set
problem [12, 16]. Max-Min and Max-Sum p-dispersion problems are still NP-hard
problems when distances fulfill the triangle inequality [12, 16]. The planar
(2d) Max-Min p-dispersion problem is also NP-hard [33], the NP-hardness of the
planar Max-Sum p-dispersion problem is still an open question to the best of
our knowledge. The one-dimensional (1d) cases of Max-Min and Max-Sum
p-dispersion problems are solvable in polynomial time, with a similar DP
algorithm running in $O(\max\\{pn,n\log n\\})$ time [27, 33]. Complexity
results have also been proven for the APX classes of several variants of
p-dispersion problems. Firstly, for all $\alpha>1$, any $\alpha$-approximation
for the Max-Min p-dispersion problem is NP-hard in the general case [27]. In
two specific cases, 2d or having triangle inequality, it exists a
$2$-approximation for the Max-Min p-dispersion problem [27]. For all
$\alpha<2$, any $\alpha$-approximation for the Max-Min p-dispersion problem
with triangle inequality is NP-hard [27].

Although, p-dispersion is mentioned to have relevant applications for MOO [13,
27], no specific studies concerned the p-dispersion in a PF to the best of our
knowledge. We note that an affine 2d PF is a line in ${\mathbb{R}}^{2}$, such
case is equivalent to the 1d case. Hence, Max-Min and Max-Sum p-dispersion
problems are solvable in $O(\max\\{pn,n\log n\\})$ time thanks to [27, 33].
General planar cases of p-dispersion problems can also be seen as specific
cases of three-dimensional (3d) PF, affine 3d PF. Having a NP-hard complexity
proven for the planar cases of Max-Min p-dispersion, it implies that the Max-
Min p-dispersion problem is also NP-hard for 3d PF.

###  3.2 Exact methods to solve p-dispersion problems

The Max-Sum p-dispersion problem can be formulated as a quadratic optimization
problem, defining binary variables $z_{j}\in\\{0,1\\}$ with $z_{j}=1$ if and
only if the point $x_{j}$ is selected:

$\begin{array}[]{llrllr}{\mathcal{P}}_{disp}^{MS}(E,p)&=&\max\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}d_{i,j}&z_{i}z_{j}&&(\ref{mathProgMaxSumDispersion}.1)\\\
&s.t:&\sum_{j=1}^{n}z_{j}&=p&&(\ref{mathProgMaxSumDispersion}.2)\\\
&&z_{j}&\in\\{0,1\\}\hskip 19.91684pt&\forall
j\in[\\![1,n]\\!],&(\ref{mathProgMaxSumDispersion}.3)\end{array}$ (11)

The linearization of (11.3) leads to the Integer Linear Programming (ILP)
formulation provided by [20]. Mathematical programming formulations are also
used in exact Branch&Bound (B& B) algorithms iterating with the computations
of upper and lower bounds, with a Lagrangian relaxation in [1] or with upper
bounds computable in $O(n^{3}$) in [26].

Similarly, the Max-Min p-dispersion problem can be modeled using non linear
optimlization ([26]):

$\begin{array}[]{llrllr}{\mathcal{P}}_{disp}^{MM}(E,p)&=\displaystyle\max_{d\geqslant
0}&d&&&(\ref{mathProgDispersion}.1)\\\
&s.t:&\sum_{j=1}^{n}z_{j}&=p&&(\ref{mathProgDispersion}.2)\\\
&&dz_{i}z_{j}&\geqslant d_{i,j}&\forall 1\leqslant i<j\leqslant
n,&(\ref{mathProgDispersion}.3)\\\ &&z_{j}&\in\\{0,1\\}\hskip
19.91684pt&\forall j\in[\\![1,n]\\!],&(\ref{mathProgDispersion}.4)\end{array}$
(12)

The standard linearization of constraints (12.3) leads to the Mixed Integer
Linear Programming (MILP) formulation provided by [20]. Another MILP
formulation was proposed, to speed-up the resolution using straightforward B&
B solving and implementing specific cuts in a Branch&Cut algorithm [28].
Decomposition schemes from [1] and [26]. can also be extended for the Max-Min
p-dispersion problem.

Similarly, MILP formulations were designed for the Max-Sum-Min and Max-Min-Sum
p-dispersion variants [13]. Such variants were less studied, a recent work
proposed a unified MILP formulation and B&B algorithm for the four variants of
p-dispersion problems [22].

###  3.3 Clustering/selecting points in Pareto frontiers

We summarize here results related to the selection or the clustering of points
in PF, with applications to MOO algorithms. Maximizing the quality of discrete
representations of Pareto sets was studied with the hypervolume measure in the
Hypervolume Subset Selection (HSS) problem [2, 29]. The HSS problem,
maximizing the representativity of $k$ solutions among a PF of size $n$
initial ones, is known to be NP-hard in dimension 3 (and greater dimensions)
since [3]. An exact algorithm in $n^{O(\sqrt{k})}$ and a polynomial-time
approximation scheme for any constant dimension $d$ are also provided in [3].
The 2d case is solvable in polynomial time thanks to a DP algorithm with a
complexity in $O(kn^{2})$ time and $O(kn)$ space provided in [2]. The time
complexity of the DP algorithm was improved in $O(kn+n\log n)$ by [4] and in
$O(k(n-k)+n\log n)$ by [21].

Some similar results were also proven for clustering problems. k-median and
k-medoid problems are known to be NP hard in dimension 2 since [24]. The
specific case of 2d PF were proven to be solvable in $O(n^{3})$ time with DP
algorithms [9, 7]. The 1d case are solvable in $O(nk)$ time [17]. K-means, one
of the most famous unsupervised learning problem, is also NP-hard for 2d cases
[23]. The restriction to 2d PF would be also solvable in $O(n^{3})$ time with
a DP algorithm if a conjecture is proven [6]. The 1d case of k-means is also
solvable by a DP algorithm, with a complexity in $O(kn)$ using memory space in
$O(n)$ [15]. For k-means, k-medoids, k-median, significant differences in the
complexities exist between the 2d PF and 1d cases.

Lastly, p-center problems present also similar results. The discrete and
continuous p-center problems are NP-hard in general, the discrete p-center
problem in ${\mathbb{R}}^{2}$ with a Euclidian distance is also NP-hard [24].
The 1d case of continuous p-center is solvable in $O(pn\log n)$ time and
$O(n)$ space [18], which is the same complexity for continuous p-center
problems in a 2d PF [8]. The discrete p-center problem in a 2d PF is solvable
$O(pn\log^{2}n)$ time and $O(n)$ space [8]. For p-center problems, the
complexity for 2d PF problems is similar to the one from 1d cases, i.e. affine
2d PF.

##  4 Intermediate results

This section presents intermediate results required for the following
developments. Firstly, Lemma 1 extends trivially the properties of $\leqslant$
and $<$ in ${\mathbb{R}}$:

###### Lemma 1

$\preccurlyeq$ is an order relation, and $\prec$ is a transitive relation:

$\forall x,y,z\in{\mathbb{R}}^{2},\phantom{3}x\prec
y\phantom{1}\mbox{and}\phantom{1}y\prec z\Longrightarrow x\prec z$ (13)

Lemma 1 implies an order among the points of $E$, for a reindexation in
$O(n.\log n)$ time:

######  Proposition 1 (Total order)

Points $(x_{i})$ can be indexed such that:

$\displaystyle\forall(i_{1},i_{2})\in[\\![1;n]\\!]^{2},$ $\displaystyle
i_{1}<i_{2}\Longrightarrow$ $\displaystyle x_{i_{1}}\prec x_{i_{2}}$ (14)
$\displaystyle\forall(i_{1},i_{2})\in[\\![1;n]\\!]^{2},$ $\displaystyle
i_{1}\leqslant i_{2}\Longrightarrow$ $\displaystyle x_{i_{1}}\preccurlyeq
x_{i_{2}}$ (15)

This property is stronger than the property that $\preccurlyeq$ induces a
total order in $E$. Furthermore, the complexity of the sorting reindexation is
in $O(n\log n)$

Proof: We reindex $E$ such that the first coordinate is increasing:

$\forall(i_{1},i_{2})\in[\\![1;n]\\!]^{2},i_{1}<i_{2}\Longrightarrow
x_{i_{1}}^{1}<x_{i_{2}}^{1}$

This sort has a time complexity in $O(n\log n)$. Let
$(i_{1},i_{2})\in[\\![1;n]\\!]^{2}$, with $i_{1}<i_{2}$. We have thus
$x_{i_{1}}^{1}<x_{i_{2}}^{1}$. Having $x_{i_{1}}\mathcal{I}x_{i_{2}}$ implies
$x_{i_{1}}^{2}>x_{i_{2}}^{2}$. $x_{i_{1}}^{1}<x_{i_{2}}^{1}$ and
$x_{i_{1}}^{2}>x_{i_{2}}^{2}$ is by definition $x_{i_{1}}\prec x_{i_{2}}$.
$\square$

$\emph{Obj}_{1}$$\emph{Obj}_{2}$$x_{1}$$\bullet$$x_{2}$$\bullet$$x_{3}$$\bullet$$x_{4}$$\bullet$$x_{5}$$\bullet$$x_{6}$$\bullet$$x_{7}$$\bullet$$x_{8}$$\bullet$$x_{9}$$\bullet$$x_{10}$$\bullet$$x_{11}$$\bullet$$x_{12}$$\bullet$$x_{13}$$\bullet$$x_{14}$$\bullet$$x_{15}$$\bullet$
Figure 1: Illustration of a 2d PF with 15 points and the indexation implied by
Proposition 1

The re-indexation of Proposition 1 implies a monotony for the distances in the
2d PF:

###### Proposition 2

We suppose that points $(x_{i})$ are sorted following Proposition 1.

$\displaystyle\forall(i_{1},i_{2},i_{3})\in[\\![1;n]\\!]^{3},\;\;\;$
$\displaystyle i_{1}\leqslant i_{2}<i_{3}\Longrightarrow
d_{i_{1},i_{2}}<d_{i_{1},i_{3}}$ (16)
$\displaystyle\forall(i_{1},i_{2},i_{3})\in[\\![1;n]\\!]^{3},\;\;\;$
$\displaystyle i_{1}<i_{2}\leqslant i_{3}\Longrightarrow
d_{i_{2},i_{3}}<d_{i_{1},i_{3}}$ (17)

Proof: We index $E$ following Proposition 1. Let’s prove it implies (16), (17)
is similar with (16). Let $i_{1}<i_{2}<i_{3}$. We note
$x_{i_{1}}=(x^{1}_{i_{1}},x^{2}_{i_{1}})$,
$x_{i_{2}}=(x^{1}_{i_{2}},x^{2}_{i_{2}})$ and
$x_{i_{3}}=(x^{1}_{i_{3}},x^{2}_{i_{3}})$ . (14) implies
$x^{1}_{i_{1}}<x^{1}_{i_{2}}<x^{1}_{i_{3}}$ and
$x^{2}_{i_{1}}>x^{2}_{i_{2}}>x^{2}_{i_{3}}$.
Hence, $(x^{1}_{i_{1}}-x^{1}_{i_{2}})^{2}<(x^{1}_{i_{1}}-x^{1}_{i_{3}})^{2}$
and $(x^{2}_{i_{1}}-x^{2}_{i_{2}})^{2}<(x^{2}_{i_{1}}-x^{2}_{i_{3}})^{2}$.
$d(x_{i_{1}},x_{i_{2}})^{2}={(x^{1}_{i_{1}}-x^{1}_{i_{2}})^{2}+(x^{2}_{i_{1}}-x^{2}_{i_{2}})^{2}}<d(x_{i_{1}},x_{i_{3}})^{2}$.
Having $\alpha>0$, it implies
$d(x_{i_{1}},x_{i_{2}})^{\alpha}<d(x_{i_{1}},x_{i_{3}})^{\alpha}$ which proves
(16). $\hfill\square$

Proposition 2 allows to reformulate Max-Min and Max-Sum-Min p-dispersion
problems:

###### Proposition 3

Let $E=\\{z_{1},\dots,z_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\prec x_{j}$. The Max-Min and Max-Sum-Min
p-dispersion problems in $E$ are also defined with:

${\mathcal{P}}_{disp}^{MM}(E,p)=\max_{1\leqslant i_{1}<\dots<i_{p}\leqslant
p}\phantom{2}\min_{j\in[\\![1;p-1]\\!]}d_{i_{j},i_{j+1}}$ (18)
${\mathcal{P}}_{disp}^{MSM}(E,p)=\max_{1\leqslant i_{1}<\dots<i_{p}\leqslant
p}\phantom{2}\sum_{i=1}^{p}\min(d_{i_{j},i_{j+1}},d_{i_{j},i_{j-1}})$ (19)

Proof: In the last minimization of problems (7) and (9), distances
$d_{i_{j},i_{j^{\prime}}}$ are considered. Such distances are minimized by
$d_{i_{j},i_{j+1}}$ and $d_{i_{j^{\prime}},i_{j^{\prime}+1}}$ using
Proposition 2, and it remains only distances among consecutive points.
$\hfill\square$

Furthermore, Proposition 2 allows to define a new variant of the Max-Sum-Min
p-dispersion problem, denoted as the Max-Sum-Neighbor p-dispersion problem or
p-dispersion-MSN:

###### Definition 1

Let $E=\\{z_{1},\dots,z_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\prec x_{j}$. The Max-Sum-Neighbor
p-dispersion, also denoted p-dispersion-MSN, can be defined in the 2d PF $E$
summing only the distances between neighbor points:

${\mathcal{P}}_{disp}^{MSN}(E,p)=\max_{1\leqslant
i_{1}<i_{2}<\dots<i_{p}\leqslant p}\sum_{i=1}^{p-1}d_{i_{j},i_{j+1}}$ (20)

The dispersion definitions after the Proposition 3 are illustrated in Table 1.
With the order of Proposition 1 and the monotony of Proposition 2,
p-dispersion-MSM is not a symmetric expression of the distances, inducing more
importance to extreme distances AB and CD. On the contrary, p-dispersion-MSN
induces symmetrical expressions. This motivated the introduction of
p-dispersion-MSN in the specific case of a 2d PF.

Table 1: Illustration of the Proposition 3 and the difference of the dispersion functions: we consider the 4-dispersion problems, with four selected points, A,B,C and D such that $A\prec B\prec C\prec D$. Dispersion type |  | Dispersion of A,B,C,D
---|---|---
p-dispersion-MM | : |  $\min$(AB,BC,CD)
p-dispersion-MS | : | AB+AC+AD+BC+BD+CD
p-dispersion-MSN | : | AB+BC+CD
p-dispersion-MSM | : | AB+min(AB,BC) +min(BC,CD) +CD
p-dispersion-MMS | : | min(AB+AC+AD,AB+BC+BD,AD+BD+CD)

Propositions 1 and 2 allow to get first polynomial results in Propositions 4,
6 and 7 present some polynomial complexity results. A key element is that the
extreme points of the 2d PF are natural candidates for p-dipersion problems,
as analyzed in Propositions 4 and 5:

######  Proposition 4 (2-dispersion problems)

Let $E=\\{z_{1},\dots,z_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $z_{i}{\mathcal{I}}z_{j}$. 2-dispersion problems
are solvable in $O(n)$ time using $O(1)$ additional memory space in the 2d PF
$E$, considering variants (7), (8), (9), (10) or (20). There is a unique
optimal solution, selecting $z_{1}$ and $z_{n}$.

Proof: Considering variants (7), (8), (9), (10) or (20), the same problem must
be solved:

${\mathcal{P}}_{2}(E)=\max_{1\leqslant i<j\leqslant p}d(z_{i},z_{j})$ (21)

Indeed,
${\mathcal{P}}_{disp}^{MM}(E,2)={\mathcal{P}}_{disp}^{MS}(E,2)={\mathcal{P}}_{disp}^{MMS}(E,2)={\mathcal{P}}_{disp}^{MSN}(E,2)={\mathcal{P}}_{2}(E)$
and ${\mathcal{P}}_{disp}^{MSM}(E,2)=2{\mathcal{P}}_{2}(E)$. Using Proposition
2, it is trivial that there is a unique optimal solution to (21), selecting
the two extreme points $z_{1}$ and $z_{n}$ after the re-indexation of
proposition 1, with a optimal cost $d_{1,n}$. The complexity, once having
computed $z_{1}$ and $z_{n}$ is in $O(1)$ time and additional space. Re-
indexing the whole PF would induce a complexity in $O(n\log n)$ time.
Actually, there is no need for a full re-indexation, computing the extreme
points can be done in one traversal of $E$, inducing a complexity in $O(n)$
time. $\hfill\square$

######  Proposition 5 (p-dispersion and extreme points)

Considering variants (7), (8), (9), (10) or (20), an optimal solution of
p-dispersion can be considered selecting $x_{1}$ and $x_{n}$ for $p\geqslant
2$ once points $(x_{i})$ are re-indexed as in Proposition 1. Reciprocally, any
optimal solution contains the extreme points in the case of the Max-Sum and
Max-Sum-Neighbor variants, contrary to the Max-Min, Max-Sum-Min and Max-Min-
Sum variants where counter-examples exist.

Proof: Considering variants (7), (8), (9), (10) or (20), let $1\leqslant
i_{1}<i_{2}<\dots<i_{p}\leqslant p$ the indexes defining an optimal solution.
Considering new indexes $i_{1}^{\prime}=1,i_{2}^{\prime}=i_{2},\dots
i_{p-1}^{\prime}=i_{p-1},i_{p}^{\prime}=p$, we have thanks to Proposition 2
$d(i_{j_{1}},i_{j_{2}})^{\alpha}\leqslant
d(i_{j_{1}}^{\prime},i_{j_{2}}^{\prime})^{\alpha}$. It implies that the points
defined with new indexes have at least the same dispersion than the original
points. The new points define necessarily an optimal solution of the
considered variant of p-dispersion.
In the case of Max-Sum and Max-Sum-Neighbor p-dispersion problems, having an
optimal solution with $1<i_{1}$ or $i_{p}<p$ induces that we have furthermore
$d(i_{1},i_{2})^{\alpha}+d(i_{p-1},i_{p})^{\alpha}<d(i_{1}^{\prime},i_{j_{2}}^{\prime})^{\alpha}+d(i_{p-1}^{\prime},i_{p}^{\prime})^{\alpha}$,
and the new construction of points with indexes $i^{\prime}$ induces a
strictly better solution. So, an optimal solution of Max-Sum and Max-Sum-
Neighbor p-dispersion problems contains necessarily the extreme points.
Lastly, a counter example of the reciprocity with Max-Min 3-dispersion and 4
points in a 2d PF is given with: $z_{1}=(0,10)$, $z_{2}=(1,9)$, $z_{3}=(3,7)$,
$z_{4}=(5,5)$.$\hfill\square$

Remark: This property of p-dispersion is relevant in the selection of points
of a PF for human decision makers. Indeed, it is natural to present the
extreme points to evaluate the preferences of the decision maker. This is a
justification to use p-dispersion in that goal instead of clustering measure
like k-medoids, which would not furnish the extreme points [7].

Proposition 5 is useful to determine the complexity of $3$-dispersion
problems, and also improve the general complexity enumerating all the
possibilities, that would be in $O(n^{p})$.

######  Proposition 6 (3-dispersion)

$3$-dispersion problems in a 2d PF are solvable in $O(n)$ time using $O(1)$
additional space.

Proof:Considering variants (7), (8), (9), (10) or (20), we consider the two
extreme points, which can be found in $O(n)$ time with one traversal of $E$
like in Proposition 4. Then, there are $n-2$ cases to enumerate the last
point, each cost computation of 3-dispersion being in $O(1)$ time, this last
naive enumeration is in $O(n)$ time. $3$-dispersion problems are thus solved
in $O(n)$ time using $O(1)$ additional space with two traversals of
$E$.$\hfill\square$

######  Proposition 7 (p-dispersion)

The $p$-dispersion problems in a 2d PF are solvable in $O(n^{p-2})$ time using
$O(1)$ additional space.

Proof: Similarly with Proposition 6, once the extreme points are found in
$O(n)$ time, the naive enumeration of the other $p-2$ selected points induces
${n-2}\choose{p-2}$ computations, requiring $O(p)$ or $O(p^{2})$ time
computations.$\hfill\square$

##  5  p-dispersion-MSN is polynomially solvable

Proposition 2 allows to prove Bellman equations for the p-dispersion-MSN
problem in a 2d PF, which is the key ingredient to design a DP algorithm:

######  Proposition 8 (Bellman equations for p-dispersion-MSN)

Defining $C_{k,i}^{MSN}$ as the optimal cost of $k$-dispersion-MSN among the
points indexed in $[\\![1,i]\\!]$ for all $k\in[\\![2,p]\\!]$ and
$i\in[\\![k,n]\\!]$, we have:

$\forall i\in[\\![1,n]\\!],\>\>\>C^{MSN}_{2,i}=d_{1,i}$ (22) $\forall
i\in[\\![1,n]\\!],\>\forall
k\in[\\![3,p]\\!],\>\>\>C^{MSN}_{k,i}=\max_{j\in[\\![k-1,i-1]\\!]}(C^{MSN}_{k-1,j}+d_{j,i})$
(23)

Proof: (22) is given by Proposition 4. We suppose $k\geqslant 3$ and prove
(23). Let $i\in[\\![k,n]\\!]$. Selecting for each $j\in[\\![k-1,i-1]\\!]$ an
optimal solution of $(k-1)$-dispersion-MSN among points indexed in
$[\\![1,j]\\!]$, and adding point $i$, it makes a feasible solution for
$(k-1)$-dispersion-MSN among points indexed in $[\\![1,i]\\!]$ with a cost
$C^{MSN}_{k-1,j}+d_{j,i}$. This last cost is lower than the optimal $k$
dispersion cost, thus $C^{MSN}_{k,i}\geqslant C^{MSN}_{k-1,j}+d_{j,i}$.

$C^{MSN}_{k,i}\geqslant\max_{j\in[\\![k-1,i-1]\\!]}(C^{MSN}_{k-1,j}+d_{j,i})$
(24)

Let $j_{1},j_{2},\dots,j_{k-1},j_{k}$ indexes such that
$1=j_{1}<j_{2}<\dots<j_{k-1}<j_{k}=i$ defines an optimal solution of
$k$-dispersion-MSN, its cost is $C^{MSN}_{k,i}$. Necessarily,
$j_{1},j_{2},\dots,j_{k-1}$ defines an optimal solution of $(k-1)$-dispersion-
MSN among points indexed in $[\\![1,j_{k-1}]\\!]$. On the contrary, a strictly
better solution for $C^{MSN}_{k,i}$ would be constructed adding the index $i$.
We have thus: $C^{MSN}_{k,i}=C^{MSN}_{k-1,j_{k-1}}+d_{j_{k-1},i}$. Combined
with (24), it proves :
$C^{MSN}_{k,i}=\max_{j\in[\\![k-1,i-1]\\!]}(C^{MSN}_{k-1,j}+d_{j,i})$.
$\hfill\square$

It allows to design a DP algorithm for p-dispersion-MSN in Algorithm 1. The
first phase constructs by induction the matrix of optimal costs
$C^{MSN}_{k,i}$ with $k$ increasing. $C^{MSN}_{p,n}$ is the optimal value of
MSN p-dispersion. Then, backtracking operations in the matrix $C^{MSN}_{k,i}$
return an optimal solution.

Algorithm 1: p-dispersion-MSN in a 2d PF with $p>3$
---
Input:
\- $n$ points of ${\mathbb{R}}^{2}$, $E=\\{x_{1},\dots,x_{n}\\}$ such that for
all $i_{1}<i_{2}$, $x_{i_{1}}\phantom{0}\mathcal{I}\phantom{0}x_{i_{2}}$ ;
\- an integer $p$ with $3<p\leqslant N$.
initialize matrix $C$ with $C_{k,i}:=0$ for all
$i\in[\\![1;N]\\!],k\in[\\![2;p-1]\\!]$
for $i=1$ to $N-1$:
$C_{2,i}:=d_{1,i}$
end for
for $k=3$ to $p-1$ :
for $i=1$ to $N-1$:
$C_{k,i}:=\max_{j\in[\\![k-1,i-1]\\!]}(C_{k-1,j}+d_{j,i})$
end for
end for
$OPT:=\max_{j\in[\\![p-1,N-1]\\!]}(C_{p-1,j}+d_{j,N})$
$j:=\mbox{argmax}_{j\in[\\![p-1,N-1]\\!]}(C_{p-1,j}+d_{j,N})$
initialize $i:=j$ and ${\mathcal{I}}:=\\{1,j,N\\}$.
for $k=p-1$ to $3$ with increment $k\leftarrow k-1$:
$j:=\mbox{argmax}_{j\in[\\![k-1,i-1]\\!]}(C_{p-1,j}+d_{j,i})$
add $j$ in ${\mathcal{I}}$
$i:=j$
end for
return $OPT$ the optimal cost and the set of selected indexes ${\mathcal{I}}$.

###### Theorem 1

Let $E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\phantom{0}\mathcal{I}\phantom{0}x_{j}$.
Max-Sum-Neighbor p-dispersion is solvable in polynomial time in the 2d PF $E$.
The cases $p=2,3$ are solvable with a complexity in $O(n)$ time using an
additional memory space in $O(1)$. Algorithm 1 solves the cases $p>3$ with a
complexity in $O(pn^{2})$ time and $O(pn)$ memory space.

Proof: The cases $p=2,3$ are given by Propositions 4, and 6, so that we
suppose $p\geqslant 4$ and we consider the Algorithm 1. The induction formula
(23) uses only values $C_{i,j}$ with $j<k$. Hence, $C_{k,n}$ is at the end of
each loop in $k$ the optimal value of the $k$-dispersion-MSN among the $n$
points of $E$, and the optimal cost. The remaining operations after the
computation of $C_{p,n}$ is a standard backtrack algorithm to return an
optimal solution. This proves the validity of Algorithm 1 to solve optimally
$p$-dispersion-MSN. Let us analyze the complexity of Algorithm 1. Re-indexing
$E$ following Proposition 1 has a time complexity in $O(n\log n)$. Computing
the line $k=2$ of the DP matrix has also a time complexity in $O(n)$.
Computing $\max_{j\in[\\![k-1,i-1]\\!]}(C_{k-1,j}+d_{j,i})$ is in $O(i-k)$ and
thus in $O(n)$ enumerating all the $i-k$ possibilities. It induces time
complexities in $O(pn^{2})$ for the construction of the DP matrix, and in
$O(pn)$ for the backtracking operations. Finally, the time complexity is given
by the construction of the DP matrix, in $O(pn^{2})$ time. The space
complexity is in $O(pn)$, storing the DP matrix $C$, the complexity is proven.
$\hfill\square$

Remark: In Algorithm 1, the DP matrix $C$ is computed line by line, with the
index $k$ increasing. The computation of line $k+1$ requires only the line $k$
and computations of distances using $O(1)$ additional memory space. If one
wishes to compute only the optimal value $C_{p,n}$, it is possible to delete
the line $k-1$ once the line $k$ is completed. Such implementation has at most
$2n$ elements in the memory, and thus a complexity in $O(n)$ memory space.
Theorem 1 states a complexity in $O(pn)$ memory space as the backtracking
operations to compute an optimal solution, as written in Algorithm 1, use the
whole DP matrix.

##  6 Max-Min p-dispersion is polynomially solvable

Proposition 2 allows also to prove Bellman equations for the Max-Min
p-dispersion problem in a 2d PF:

######  Proposition 9 (Bellman equations)

Let $E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\prec x_{j}$. Let
$E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$, such
that for all $i\neq j$, $x_{i}\prec x_{j}$. Defining $C^{MM}_{k,i}$ as the
optimal cost of Max-Min $k$-dispersion among the points indexed in
$[\\![1,i]\\!]$ for all $k\in[\\![2,p]\\!]$ and $i\in[\\![k,n]\\!]$ , we have
the following relations:

$\forall i\in[\\![1,n]\\!],\>\>\>C_{2,i}^{MM}=d_{1,i}$ (25) $\forall
k\in[\\![3,p]\\!],\>\forall
i\in[\\![k,n]\\!],\>\>\>C_{k,i}^{MM}=\max_{j\in[\\![k-1,i-1]\\!]}\min(C_{k-1,j}^{MM},d_{j,i})$
(26)

Proof: The proof is similar with the one of Proposition 8. $\hfill\square$

Remark: Similarly with Algorithm 1, equations (26) allows to design a DP
algorithm with a complexity in $O(pn^{2})$ time and $O(pn)$ space. Following
developments improve this complexity.

Algorithm 2: Computation of
$\mbox{max}_{j\in[\\![k-1,i-1]\\!]}\min(C_{k-1,j}^{MM},d_{j,i})$
---
input: indexes $k<i$
``
`` define $a:=k-1$, $b:=i-1$
`` while $b-a\geqslant 2$
`` Compute $j=\left\lfloor\frac{a+b}{2}\right\rfloor$
`` if $C_{k-1,j}^{MM}-d_{j,i}>0$ ` `then :` ` $b:=j$
`` else ` `:` ` $a:=j$
`` end while
``
`` return $\max(\min(C_{k-1,a}^{MM},d_{a,i}),\min(C_{k-1,b}^{MM},d_{b,i}))$

###### Proposition 10

Let $k\in[\\![3,p]\\!]$ and $i\in[\\![k,n]\\!]$. Algorithm 2 computes
$C_{k,i}^{MM}=\max_{j\in[\\![k-1,i-1]\\!]}\min(C_{k-1,j}^{MM},d_{j,i})$ with a
time complexity in $O(\log(i+1-k))$ once the $C_{j-1,k-1}$ are computed.

Proof: Let $k\in[\\![3,p]\\!]$ and $i\in[\\![k,n]\\!]$. Reformulating
Proposition 2, the application $j\in[\\![k-1,i-1]\\!]\mapsto d_{j,i}$ is
strictly decreasing. The application $j\in[\\![k-1,i-1]\\!]\mapsto
C_{k-1,j}^{MM}$ is increasing: any feasible solution of $(k-1)$-dispersion-MM
among the $j$ first points, is a feasible solution for $(k-1)$-dispersion-MM
considering the $j+1$ first points, and the optimal value $C_{k-1,j}^{MM}$ is
increasing. Hence, $\varphi_{i,k}:j\in[\\![k-1,i-1]\\!]\mapsto
C_{k-1,j}^{MM}-d_{j,i}$ is strictly increasing. Let
$\psi_{i,k}:j\in[\\![k-1,i-1]\\!]\mapsto\min(C_{k-1,j}^{MM},d_{j,i})$ .
$\varphi_{i,k}(i-1)=C_{i,k-1}^{MM}>0$. Let
$\alpha=\min\\{j\in[\\![k-1,i-1]\\!],\varphi_{i,k}(j)\geqslant 0\\}$. For
$j\geqslant\alpha$, $\psi_{i,k}(j)=C_{k-1,j}^{MM}$, and $\psi_{i,k}$ is
increasing for $j\geqslant\alpha$. For $j<\alpha$,
$\psi_{i,k}(j)=C_{k-1,j}^{MM}$, and $\psi$ is strictly decreasing for
$j<\alpha$. Hence, $\psi_{i,k}$ reaches a minimum for $j=\alpha$ or
$j=\alpha-1$.

The computation of $\alpha$, as the minimal value such that
$\varphi_{i,k}(j)\geqslant 0$, can be solved with a dichotomic search
presented in Algorithm 2, for a time complexity in $O(\log(i+1-k))$.
$\hfill\square$

Proposition 10 allows to improve the time complexity of the DP algorithm for
Max-Min p-dispersion problem. The following developments improve the space
complexity. Similarly with the remark page 1 for p-dispersion-MSN, the final
cost $C_{p,n}^{MM}$ can be constructed using a memory space in $O(n)$,
deleting the line $k$ of the DP matrix when the line $k+1$ is fully computed.
The point here is to provide backtracking algorithms which do not require to
have stored the whole DP matrix $C_{k,i}^{MM}$, with a complexity in at most
$O(n)$ memory space and $O(pn\log n)$ time. Algorithm 3 and 3’ compute optimal
solutions of p-dispersion-MM knowing the optimal cost OPT, with greedy
strategies:

Algorithm 3: Backtracking algorithm using $O(n)$ memory space
---
input:
``\- $n$ points of a 2d PF, $E=\\{z_{1},\dots,z_{n}\\}$, sorted such that for
all $i<j$, $z_{i}\prec z_{j}$ ;
``\- $p\in{\mathbb{N}},p>2$;
``\- $OPT$, the optimal cost of Max-Min $p$-dispersion;
``
`` initialize $M:=1$, $m:=1$, ${\mathcal{I}}=\\{1,n\\}$.
`` for $k=2$ to $p-1$ with increment $k\leftarrow k+1$
`` $M$ := the smallest index such that $d(x_{m},x_{M})\geqslant OPT$
`` add $M$ in ${\mathcal{I}}$
`` $m:=M$
`` end for
return ${\mathcal{I}}$

Algorithm 3’: Backtracking algorithm using $O(n)$ memory space
---
input:
``\- $n$ points of a 2d PF, $E=\\{z_{1},\dots,z_{n}\\}$, sorted such that for
all $i<j$, $z_{i}\prec z_{j}$ ;
``\- $p\in{\mathbb{N}},p>2$;
``\- $OPT$, the optimal cost of Max-Min $p$-dispersion;
``
`` initialize $M:=n$, $m:=n$, ${\mathcal{I}}=\\{1,n\\}$.
`` for $k=p-1$ to $2$ with increment $k\leftarrow k-1$
`` $m$ := the biggest index such that $d(x_{m},x_{M})\geqslant OPT$
`` add $m$ in ${\mathcal{I}}$
`` $M:=m$
`` end for
return ${\mathcal{I}}$

###### Proposition 11

Let $p\in{\mathbb{N}},p\geqslant 3$. Let $E=\\{z_{1},\dots,z_{n}\\}$, sorted
such that for all $i<j$, $z_{i}\phantom{0}\prec\phantom{0}z_{j}$. Once the
optimal cost of Max-Min p-dispersion problem is computed, Algorithm 3 and 3’
computes an optimal partition in $O(p\log n)$ time using $O(1)$ additional
memory space. Furthermore, let $j_{1}=1,j_{2},\dots,j_{p-1},j_{p}=n$ the
indexes of an optimal solution, let $1,i_{2},\dots,i_{p-1},n$ (resp
$1,i_{2}^{\prime},\dots,i_{p-1}^{\prime},n$) the indexes given by Algorithm 3
(resp 3’). We have: for all $k\in[\\![2,p-1]\\!],i_{k}\leqslant j_{k}\leqslant
i^{\prime}_{k}$. In other words, the indexes given by Algorithm 3 (resp 3’)
are lower (resp upper) bounds of the indexes of any optimal solution of Max-
Min p-dispersion considering the extreme points $z_{1}$ and $z_{n}$.

Proof: We prove the result for Algorithm 3, the proof is similar for Algorithm
3’. Let $j_{1}=1,j_{2},\dots,j_{p-1},j_{p}=n$ the indexes of an optimal
solution, let $i_{1}=1,i_{2},\dots,i_{p-1},i_{p}=n$ the indexes given by
Algorithm 3. Firstly, We prove by induction on $k$ that for all
$k\in[\\![1,p-1]\\!],i_{k}\leqslant j_{k}$. The case $k=1$ is given by
$j_{1}=i_{1}=1$. We suppose $k>1$ and that the induction hypothesis is true or
$k-1$, i.e. $i_{k-1}\leqslant j_{k-1}$. $i_{k}$ is the smallest index such
that $d(x_{i_{k}},x_{i_{k-1}})\geqslant OPT$. Using Proposition 2,
$d(x_{j_{k}},x_{j_{k-1}})\leqslant d(x_{j_{k}},x_{j_{i-1}})$.
$i_{k-1}>j_{k-1}$ would be in contradiction with
$d(x_{j_{k}},x_{j_{k-1}})\geqslant OPT$ and the definition of $i_{k}$ as the
smallest index such that $d(x_{i_{k}},x_{i_{k-1}})\geqslant OPT$. We have also
$i_{k}\leqslant j_{k}$, which terminates the induction proof that indexes
$i_{k}$ are lower bounds of indexes $j_{k}$.

let us prove that indexes $i_{1}=1,i_{2},\dots,i_{p-1},i_{p}=n$ define an
optimal solution. We have by construction $d(x_{i_{k}},x_{i_{k-1}})\geqslant
OPT$ for all $k\in[\\![1,p-1]\\!]$, we have just to prove that
$d(x_{n},x_{i_{p-1}})\geqslant OPT$. $i_{p-1}\leqslant j_{p-1}\leqslant
n=j_{p}=i_{p}$. Using Proposition 2, $d(x_{n},x_{i_{p-1}})\geqslant
d(x_{n},x_{j_{p-1}})$. The optimality implies $d(x_{n},x_{j_{p-1}})\geqslant
OPT$, and thus $d(x_{n},x_{i_{p-1}})\geqslant OPT$. Algorithm 3 returns the
optimal solution with the minimal indexes, let’s analyze the complexity.
Algorithm 4 calls at most $p-2$ times the computation of smallest index
$i_{k}$ such that $d(x_{i_{k}},x_{i_{k-1}})\geqslant OPT$, which can be
proceeded with a dichotomic search. Hence, Algorithm 3 runs in $O(p\log n)$
time. $\hfill\square$ Proposition 11 allows to define in Algorithm 4 a valid
DP algorithm for Max-Min p-dispersion running in $O(n)$ memory space. Theorem
2 summarizes the complexity results for Max-Min p-dispersion:

Algorithm 4: Max-Min p-dispersion in a 2d-PF with $p>3$
---
Input:
\- $n$ points of ${\mathbb{R}}^{2}$, $E=\\{x_{1},\dots,x_{n}\\}$ such that for
all $i_{1}<i_{2}$, $x_{i_{1}}\phantom{0}\mathcal{I}\phantom{0}x_{i_{2}}$ ;
\- an integer $p$ with $3<p\leqslant N$.
re-index $E$ following the order of Proposition 1
initialize line $2$ of the matrix $C$ with $C_{2,i}=0$ for all
$i\in[\\![1;n]\\!]$
for $i=1$ to $n-1$:
$C_{2,i}:=d_{1,i}$
end for
for $k=3$ to $p$ :
initialize line $k$ of the matrix $C$ with $C_{k,i}=0$ for all
$i\in[\\![k;n]\\!]$
for $i=1$ to $n-1$:
$C_{k,i}:=\displaystyle\max_{j\in[\\![k-1,i-1]\\!]}\min(C_{k-1,j},d_{j,i})$
with Algorithm 2
end for
delete line $k-1$ of the matrix $C$
end for
delete line $p$ of the matrix $C$
$OPT:=C_{p,n}$
return $OPT$ and a solution of Algorithm 3 (or Algorithm 3’)

###### Theorem 2

Let $E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\mathcal{I}x_{j}$. The Max-Min p-dispersion
problem is polynomially solvable to optimality in the 2d PF $E$. The cases
$p=2,3$ are solvable with a complexity in $O(n)$ time using an additional
memory space in $O(1)$ . With $p>3$, Algorithm 4 solves the Max-Min
p-dispersion problem with a complexity in $O(pn\log n)$ time and $O(n)$ memory
space.

Proof: The cases $p=2,3$ are given by Propositions 4 and 6, so that we suppose
$p\geqslant 4$ and we consider the Algorithm 4. The induction formula (23) in
Proposition 9 uses only values $C_{i,j}$ with $j<k$ in Algorithm 4. $C_{k,n}$
is at the end of each loop in $k$ the optimal value of the Max-Min
$k$-dispersion among the $n$ points of $E$, and the optimal cost is given by
$C_{k,n}$. The validity of the backtracking procedures is proven in
Proposition 11. Let us analyze the complexity of Algorithm 4. The space
complexity is in $O(n)$, storing at most two lines of the DP matrix $C$.
Sorting and indexing the elements of $E$ following Proposition 1 has a time
complexity in $O(n\log n)$. Computing the line $k=2$ of the DP matrix has also
a time complexity in $O(n)$. The other lines are computed in $O(n\log n)$ time
with Proposition 10, for a total computation of the DP matrix in $O(pn\log n)$
time. The backtracking operations run in $O(p\log n)$ time, so that the time
complexity is given by the computation of the DP matrix in $O(pn\log n)$ time.
$\hfill\square$

##  7 Max-Sum-Min p dispersion is polynomially solvable

Proposition 2 allows also to design Bellman equations for the p-dispersion-MSM
problem in a 2d PF:

######  Proposition 12 (Bellman equations)

Let $E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\prec x_{j}$. Let
$p\in{\mathbb{N}},p\geqslant 4$. For all $k\in[\\![3,p]\\!]$, we define
$C_{k,i,i^{\prime}}^{MSM}$ as the optimal cost of Max-Sum-Min $k$-dispersion
among the points indexed in $[\\![k,i^{\prime}]\\!]$ with $i<i^{\prime}$ being
last selected point before $i^{\prime}$. We have the following relations:

$\forall
i\in[\\![1,n]\\!],\>\>\>C_{3,i,i^{\prime}}^{MSM}=d_{i,i^{\prime}}+d_{1,i^{\prime}}+\min(d_{1,i^{\prime}},d_{i^{\prime},i})$
(27) $\forall k\in[\\![4,p]\\!],\>\forall i^{\prime}\in[\\![1,n]\\!],\>\forall
i<i^{\prime}\>\>\>C_{k,i,i^{\prime}}^{MSM}=\max_{j\in[\\![1,i-1]\\!]}C_{k-1,j,i}^{MSM}+\min(d_{j,i},d_{i^{\prime},i})$
(28)

Proof: $C_{3,i,i^{\prime}}^{MSM}$ is not an optimization problem with
Proposition 5, there is a unique solution to consider: selecting,
$1,i^{\prime},i$. This makes the dispersion given in (27). Let
$k\in[\\![4,p]\\!]$, let $i\in[\\![k,n-1]\\!]$, let
$i^{\prime}\in[\\![i+1,n]\\!]$. Selecting for each $j\in[\\![k-1,i-1]\\!]$ an
optimal solution of $(k-1)$-dispersion-MSM among points indexed in
$[\\![1,i]\\!]$ with $j$ as last selected point before $i$, and adding point
$i$, it makes a feasible solution for $(k-1)$-dispersion-MSM among points
indexed in $[\\![1,i]\\!]$ with a cost
$C_{k-1,j,i}^{MSM}+\min(d_{j,i},d_{i^{\prime},i})$. This last cost is lower
than the optimal $k$ dispersion cost, thus $C_{k,i,i^{\prime}}^{MSM}\geqslant
C_{k-1,j,i}^{MSM}+\min(d_{j,i},d_{i^{\prime},i})$.

$C_{k,i,i^{\prime}}^{MSM}\geqslant\max_{j\in[\\![1,i-1]\\!]}C_{k-1,j,i}^{MSM}+\min(d_{j,i},d_{i^{\prime},i})$
(29)

Let $j_{1},\dots,j_{k}$ indexes such that $1\leqslant
j_{1}<j_{2}<\dots<j_{k-1}=i<j_{k}=i^{\prime}$ defining an optimal solution of
$k$-dispersion-MSM in $[\\![1,i^{\prime}]\\!]$ with $i$ as last selected point
before $i^{\prime}$, its cost is $C_{k,i,i^{\prime}}^{MSM}$. Necessarily,
$j_{1},j_{2},\dots,j_{k-1}$ defines an optimal solution of $(k-1)$-dispersion-
MSM among points indexed in $[\\![1,i]\\!]$ with $j_{k-2}$ as last selected
point before $i$. On the contrary, a strictly better solution for
$C_{k,i,i^{\prime}}^{MSM}$ would be constructed adding the index $i^{\prime}$.
We have thus:
$C_{k,i,i^{\prime}}^{MSM}=C_{k-1,j_{k-2},i}^{MSM}+\min(d_{j_{k-2},i},d_{i^{\prime},i})$.
Combined with (29), it proves :
$C^{MSN}_{k,i}=\max_{j\in[\\![k-1,i-1]\\!]}C_{k-1,j,i}^{MSM}+\min(d_{j,i},d_{i^{\prime},i})$.
$\hfill\square$

Algorithm 5: Max-Sum-Min p-dispersion in a 2d-PF with $p>5$
---
Input:
\- $n$ points of ${\mathbb{R}}^{2}$, $E=\\{x_{1},\dots,x_{n}\\}$ such that for
all $i_{1}<i_{2}$, $x_{i_{1}}\prec x_{i_{2}}$ ;
\- an integer with $5<p\leqslant N$.
initialize matrix $C$ with $C_{k,i,i^{\prime}}:=0$ for all
$i\in[\\![0;n]\\!],k\in[\\![2;p-1]\\!]$
re-index $E$ following the order of Proposition 1
for $i=1$ to $n-1$
for $i^{\prime}=1$ to $i-1$
$C_{3,i,i^{\prime}}^{MSM}:=d_{i,i^{\prime}}+d_{1,i^{\prime}}+\min(d_{1,i^{\prime}},d_{i^{\prime},i})$
for $k=4$ to $p-1$
$C_{k,i,i^{\prime}}:=\max_{j\in[\\![1,i-1]\\!]}C_{k-1,j,i}+\min(d_{j,i},d_{i^{\prime},i})$
end for
end for
$OPT:=\max_{j\in[\\![p-1,N-1]\\!]}C_{p,j,N}$
$j:=\mbox{argmax}_{j\in[\\![p-1,N-1]\\!]}C_{p,j,N}$
initialize $i^{\prime}:=N$, $i:=j$ and ${\mathcal{I}}:=\\{1,j,N\\}$.
for $k=p-1$ to $3$ with increment $k\leftarrow k-1$
find $j\in[\\![1,i-1]\\!]$ such that
$C_{k,i,i^{\prime}}=\max_{j\in[\\![1,i-1]\\!]}C_{k-1,j,i}+\min(d_{j,i},d_{i^{\prime},i})$
add $j$ in ${\mathcal{I}}$
$i^{\prime}:=i$
$i:=j$
end for
return $OPT$ the optimal cost and the set of selected indexes ${\mathcal{I}}$.

###### Theorem 3

Let $E=\\{x_{1},\dots,x_{n}\\}$ a subset of $n$ points of ${\mathbb{R}}^{2}$,
such that for all $i\neq j$, $x_{i}\mathcal{I}x_{j}$. Max-Sum-Min p-dispersion
is polynomially solvable to optimality in the 2d PF $E$. The cases $p=2,3$ are
solvable with a complexity in $O(n)$ time using an additional memory space in
$O(1)$ . The cases $p=4$ (resp $p=5$) are solvable with a complexity in
$O(n^{2})$ (resp $O(n^{3})$) time using an additional memory space in $O(1)$.
In the cases $p>5$, Algorithm 5 solves Max-Sum-Min p-dispersion with a
complexity in $O(pn^{3})$ time and $O(pn^{2})$ memory space.

Proof: The cases $p=2,3,4,5$ are given by Propositions 4, and 6, so that we
suppose $p\geqslant 6$ and we consider the Algorithm 5. The proof of the
validity of Algorithm 5 to compute the optimal value and an solution for Max-
Sum-Min p-dispersion is similar with Theorems 1 and 2. Algorithm 5 computes
optimal values of $C_{k,i,i^{\prime}}^{MSM}$ with $k$ increasing requiring
only $C_{k-1,i,i^{\prime}}^{MSM}$ values. By induction, it proves that for all
$k$, $C_{k,i,i^{\prime}}^{MSM}$ has the wished optimal value at the end of the
loop $k$. The optimal value of Max-Sum-Min p-dispersion in $E$ is then given
by $\max_{j\in[\\![p-1,N-1]\\!]}C_{p,j,N}$. The remaining operations define a
standard backtrack algorithm. This proves the validity of Algorithm 5 to
return an optimal solution of $k$-dispersion-MSM. Let us analyze the
complexity. The space complexity is in $O(pn^{2})$, storing the DP matrix $C$.
The time complexity is given by the construction of the matrix
$C_{k,i,i^{\prime}}^{MSM}$, ie $O(pn^{2})$ operations running in $O(n)$ time
with naive enumerations to compute
$C_{k,i,i^{\prime}}=\max_{j\in[\\![1,i-1]\\!]}C_{k-1,j,i}+\min(d_{j,i},d_{i^{\prime},i})$.
Algorithm 5 has thus a time complexity in $O(pn^{3})$. $\hfill\square$

##  8 Discussions

This section discusses some practical applications of Theorems 1,2,3 and
Algorithms 1,4,5.

###  8.1 Comparison of DP algorithms and complexity results

Max-Min p-dispersion was proven NP-hard in 2d and solvable in
$O(\max\\{pn,n\log n\\})$ time in 1d (and thus for affine cases of 2d PF)
[33]. Theorem 2 illustrates that the PF hypothesis is crucial for the
complexity results. Max-Min p-dispersion is polynomial in a 2d PF thanks to
Proposition 1: a 2d PF can be projected in a 1d structure. The complexity in
$O(pn\log n)$ time and $O(n)$ space is not very different from the 1d case
using Max-Min p-dispersion, contrary to k-medoids and k-means problems [6, 7].
The difference in complexity from 2d PF to 1d cases are due to the triangle
inequalities in 2d PF cases, whereas 1d cases allow to use an additivity of
distances.

Bellman equations are similar for p-dispersion-MSN and p-dispersion-MM,
changing the inner minimization into a summation. A generic implementation of
Algorithm 1 for p-dispersion-MSN and p-dispersion-MM problems is possible,
with a complexity in $O(pn^{2})$ and $O(pn)$ space, which may be efficient for
practical applications. The improvements presented in section 6 are only valid
for p-dispersion-MM. On the contrary, the Bellman equations for p-dispersion-
MSM in Proposition 12 require to store the previous indexes to compute an
additive cost. The complexity in $O(pn^{3})$ time and $O(pn^{2})$ space is a
limiting factor when $n$ is large. Complexity results induces to prefer the
variant p-dispersion-MSN to the original p-dispersion-MSM for a practical
application. This was also the preference illustrated Table 1.

###  8.2 Equivalent solutions and hierarchic p-dispersion

Proposition 11 gives tight bounds on the indexes of optimal solutions of Max-
Min p-dispersion in a 2d PF. Many optimal solutions may exist for
p-dispersion-MM. Having an optimal solution, one can identify the bottleneck
distance and rearrange other selected points without changing the Max-Min
dispersion. Such situations occur when p is large enough and when the points
in the 2d PF are not well distributed. We note that the solutions of
Algorithms 3 and 3’ are very unbalanced, leading to the highest values or the
terminating distances. For a practical application, one seeks a selection of
well distributed.

To solve this issue, a bi-objective hierarchic optimization can be considered,
ranking the optimal solutions of Max-Min p-dispersion with the MSN-dispersion
function. Bellman equations of Propositions 8 and 9 can be extended to design
a DP algorithm for this hierarchic optimization. Indeed, we can define DP
matrix pairs $(C_{k,i}^{{}^{\prime}MM},C_{k,i}^{{}^{\prime}MSN})$ denoting the
optimal costs with the lexicographic order, optimizing firstly the Max-Min
k-dispersion, and then the k-dispersion-MSN among points indexed in
$[\\![1,i]\\!]$. The costs $C_{k,i}^{{}^{\prime}MM}$ are the same with the
mono-objective optimization of Max-Min p-dispersion. Such DP matrices are
constructed in $O(pn^{2})$, enumerating for each computation $i,k$ the
possible costs with an intermediate index $j$, and sorting the best current
value with the lexicographic order. The backtracking algorithm use similar
computations, as in Algorithm 1, and the hierarchic optimization is also
running in $O(pn^{2})$ time and $O(pn)$ space. One may also speed-up such cost
computations reusing the Algorithm 2 and Proposition 10, and showing that the
optimal and equivalent solutions leading to $C_{k,i}^{MM}$ are in a plateau,
ending at $\alpha$ or $\alpha-1$.

If one wishes to have an algorithm with a complexity in $O(pn\log n)$ time and
$O(n)$ space, one may try to polish the solutions given by Algorithms 3 and 3’
to have more evenly distributed distances among the consecutive selected
points. One polishing procedure is to polish locally a solution, considering
3-dispersion-MM optimizations in the consecutive points. Each 3-dispersion-MM
computation is running in $O(\log n)$ using also Proposition 10 as the points
are already sorted. This induces a quick and efficient polishing local search.

###  8.3 Parallelization issues

The time complexity in $O(pn\log n)$ or $O(pn^{2})$ can be satisfactory for
large scale computations of p-dispersion problems. For a practical speed-up,
Algorithms 1,4 and 5 have also useful properties for a parallel implementation
in multi or many-core environments. As mentioned in Theorems 1,2 and 3, the
construction of the DP matrix is the bottleneck in the time complexity, it is
crucial to parallelize carefully this phase. The backtracking algorithm is
essentially sequential, but with a low complexity, so that a parallelization
of this phase is not crucial. The initial sorting algorithm is significant in
the computation times only for the Max-Min p-dispersion problem and small
values of $p$. In this case, parallelization on General Purpose Graphical
Processing Units (GPGPU) is available [31].

In the computation of each line of the DP matrix in Algorithms 1, 4 and 5,
many operations are independent using the previous line. In Algorithm 1 (and
for the hierarchic optimization discussed in section 8.2), there are
$O(n^{2})$ independent operations. In Algorithm 5, there are $O(n^{3})$
independent operations. After the specific improvements for Max-Min
p-dispersion with Algorithms 2 and 4, there are $O(n)$ independent operations
to compute each value $C_{i,k}^{MM}$ for $i\in[\\![k,n]\\!]$ in $O(\log i)$
time. These $O(n)$ operations shall be computed from the highest values of $i$
with $i=n$ to the lowest with $i=k$, for a better load balancing following the
results of LPT (Lowest Processing Times) heuristic and approximation results
[14]. In all cases, the parallel implementation is straightforward in a shared
memory environment like OpenMP, inducing only $p-3$ synchronizations, which is
useful for the practical efficiency of parallelization.

Lastly, we note that $p$-dispersion-MM and MSN (and the hierarchic
optimization discussed in section 8.2) can be parallelized under GPGPU, with
the enumerations running in $O(pn^{2})$ time. However, the dichotomic search
in Algorithm 2 is not compatible with a GPGPU parallelization. For Max-Min
p-dispersion, one may parallelize the $O(pn\log n)$ time version with OpenMP,
or the $O(pn^{2})$ time and massively parallelized version under GPGPU.
Practical efficiency becomes dependent on the characteristic of the GPU
hardware. We note that the computation of the DP matrix line by line is an
useful point for GPGPU parallelization, using less memory space in the GPU
hardware, which may be a limiting factor.

###  8.4 Application to k-medoids/k-means clustering in a 2d PF

The exact DP algorithms for k-medoids and k-means run in $O(n^{3})$ time [6,
7]. Such complexity may be a bottleneck for the practical applications dealing
with large values of $n$. Classical heuristics for k-means/k-medoids problems
may be used in such cases, improving in quick local search procedures an
initialization of solutions [19, 30]. Such heuristics have no guarantee of
optimality, and depends heavily on the initialization strategies [19, 30]. One
may initialize these local searches with solutions of Max-Min p-dispersion to
have a quick initialization procedure using the Algorithm 4. Actually, several
initialization strategies are possible. Firstly, one can initialize the $k$
centroids using $k$-dispersion. Secondly, one can solve $2k+1$-dispersion, and
select the $k$ intermediate points following order of Proposition 1. For both
strategies, one can compute the optimal DP algorithms, or also use solutions
build by local search iterations of 3-dispersion as discussed in section 8.2.
Having many different initialization is useful for the final quality of
solutions, implementing several local searches with different initializations
in parallel environments (using Message Passing Interface protocols for a
coarse grain parallelization), as in [10].

##  9 Conclusion and perspectives

This paper examined properties of the four p-dispersion problems in a 2d PF
using Euclidian distances. A novel variant, namely Max-Sum-Neighbor
p-dispersion, is also designed specifically. The cases $p=2$ and $p=3$ induce
a complexity in $O(n)$ time with an additional memory space in $O(1)$. The
cases $p=4$ and $p=5$ have respectively time complexities in $O(n^{2})$ and
$O(n^{3})$ time with an additional memory space in $O(1)$. Such results can be
useful in the application to select a small number of representative solutions
for a decision maker. This offers another perspective, comparing the different
variants of p-dispersion in large 2d PF with small values $p$, allowing to
compare the results from [13].

Three variants are proven to be solvable in polynomial time, designing similar
DP algorithms. The Max-Sum-Min p-dispersion problem is solvable in $O(pn^{3})$
time and $O(pn^{2})$ memory space. The Max-Sum-Neighbor, is proven solvable in
$O(pn^{2})$ time and $O(pn)$ space. The standard Max-Min p-dispersion problem
is solvable in $O(pn\log n)$ time and $O(n)$ space. Furthermore, the DP
algorithms can be implemented with quasi linear speed-up with parallelization.
These results offer practical perspectives for large 2d PF, as demanded by
population meta-heuristics in bi-objective optimization. Heuristic speed-up
and quality of solutions were also discussed for such applications.

The efficiency of Max-Min p-dispersion in a 2d PF is also useful for an
application to heuristics for k-means and k-medoids clustering in a 2d PF,
where the DP algorithm has a complexity in $O(n^{3})$. Initialization
strategies can use the work on p-dispersion problems, as discussed in this
paper.

Max-Min p-dispersion is NP hard in the planar case, it is thus also the case
for three dimensional PF, there is no hope to extend the results of this paper
in dimension 3. The perspective is only to design quick heuristics for PF in
dimensions greater than 3.

## References

  * [1] S. Ağca, B. Eksioglu, and J. Ghosh.  Lagrangian solution of maximum dispersion problems.  Naval Research Logistics, 47(2):97–114, 2000.
  * [2] A. Auger, J. Bader, D. Brockhoff, and E. Zitzler.  Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences.  In Proceedings of GECCO 2009, pages 563–570. ACM, 2009.
  * [3] K. Bringmann, S. Cabello, and M. Emmerich.  Maximum volume subset selection for anchored boxes.  arXiv preprint arXiv:1803.00849, 2018.
  * [4] K. Bringmann, T. Friedrich, and P. Klitzke.  Two-dimensional subset selection for hypervolume and epsilon-indicator.  In Annual Conference on Genetic and Evolutionary Computation, pages 589–596. ACM, 2014.
  * [5] N. Dupin.  Modélisation et résolution de grands problèmes stochastiques combinatoires: application à la gestion de production d’électricité.  PhD thesis, Univ. Lille 1, 2015.
  * [6] N. Dupin, F. Nielsen, and E. Talbi.  Dynamic programming heuristic for k-means clustering among a 2-dimensional pareto frontier.  7th Internat. Conf. on Metaheuristics and Nature Inspired Computing, 2018.
  * [7] N. Dupin, F. Nielsen, and E. Talbi.  k-medoids clustering is solvable in polynomial time for a 2d Pareto front.  In World Congress on Global Optimization, pages 790–799. Springer, 2019.
  * [8] N. Dupin, F. Nielsen, and E. Talbi.  Clustering a 2d Pareto Front: p-center problems are solvable in polynomial time.  In International Conference on Optimization and Learning, pages 179–191. Springer, 2020.
  * [9] N. Dupin and E. Talbi.  Clustering in a 2-dimensional Pareto Front: p-median and p-center are solvable in polynomial time.  arXiv preprint arXiv:1806.02098, 2018.
  * [10] N. Dupin and E. Talbi.  Parallel matheuristics for the discrete unit commitment problem with min-stop ramping constraints.  International Transactions in Operational Research, 27(1):219–244, 2020.
  * [11] M. Ehrgott and X. Gandibleux.  Multiobjective combinatorial optimization - theory, methodology, and applications.  In Multiple criteria optimization: State of the art annotated bibliographic surveys, pages 369–444. Springer, 2003.
  * [12] E. Erkut.  The discrete p-dispersion problem.  European Journal of Operational Research, 46(1):48–60, 1990.
  * [13] E. Erkut and S. Neuman.  Comparison of four models for dispersing facilities.  INFOR: Information Systems and Operational Research, 29(2):68–86, 1991.
  * [14] R. Graham.  Bounds on multiprocessing timing anomalies.  SIAM journal on Applied Mathematics, 17(2):416–429, 1969.
  * [15] A. Grønlund, K. Larsen, A. Mathiasen, J. Nielsen, S. Schneider, and M. Song.  Fast exact k-means, k-medians and Bregman divergence clustering in 1d.  arXiv preprint arXiv:1701.07204, 2017.
  * [16] P. Hansen and I. Moon.  Dispersing facilities on a network.  Cahiers du GERAD, 1995.
  * [17] R. Hassin and A. Tamir.  Improved complexity bounds for location problems on the real line.  Operations Research Letters, 10(7):395–402, 1991.
  * [18] A. Karmakar, S. Das, S. Nandy, and B. Bhattacharya.  Some variations on constrained minimum enclosing circle problem.  Journal of Combinatorial Optimization, 25(2):176–190, 2013.
  * [19] S. Khan and A. Ahmad.  Cluster center initialization algorithm for k-means clustering.  Pattern recognition letters, 25(11):1293–1302, 2004.
  * [20] M.J Kuby.  Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems.  Geographical Analysis, 19(4):315–329, 1987.
  * [21] T. Kuhn, C. Fonseca, L. Paquete, S. Ruzika, M. Duarte, and J. Figueira.  Hypervolume subset selection in two dimensions: Formulations and algorithms.  Evolutionary Computation, 24(3):411–425, 2016.
  * [22] T. Lei and R. Church.  On the unified dispersion problem: Efficient formulations and exact algorithms.  European Journal of Operational Research, 241(3):622–630, 2015\.
  * [23] M. Mahajan, P. Nimbhorkar, and K. Varadarajan.  The planar k-means problem is NP-hard.  Theoretical Computer Science, 442:13–21, 2012.
  * [24] N. Megiddo and K. Supowit.  On the complexity of some common geometric location problems.  SIAM journal on computing, 13(1):182–196, 1984.
  * [25] T. Peugeot, N. Dupin, M-J Sembely, and C. Dubecq.  MBSE, PLM, MIP and Robust Optimization for System of Systems Management, Application to SCCOA French Air Defense Program.  In Complex Systems Design&Management, pages 29–40. Springer, 2017\.
  * [26] D. Pisinger.  Upper bounds and exact algorithms for p-dispersion problems.  Computers & operations research, 33(5):1380–1398, 2006.
  * [27] S. Ravi, D. Rosenkrantz, and G. Tayi.  Heuristic and special case algorithms for dispersion problems.  Operations Research, 42(2):299–310, 1994.
  * [28] D. Sayah and S. Irnich.  A new compact formulation for the discrete p-dispersion problem.  European Journal of Operational Research, 256(1):62–67, 2017.
  * [29] S. Sayın.  Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming.  Mathematical Programming, 87(3):543–560, 2000.
  * [30] E. Schubert and P. Rousseeuw.  Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms.  arXiv preprint arXiv:1810.05691, 2018.
  * [31] E. Sintorn and U. Assarsson.  Fast parallel GPU-sorting using a hybrid algorithm.  Journal of Parallel and Distributed Computing, 68(10):1381–1388, 2008.
  * [32] E. Talbi.  Metaheuristics: from design to implementation, volume 74.  Wiley, 2009.
  * [33] D. Wang and Y. Kuo.  A study on two geometric location problems.  Information processing letters, 28(6):281–286, 1988.
  * [34] E. Zio and R. Bazzo.  A clustering procedure for reducing the number of representative solutions in the pareto front of multiobjective optimization problems.  European Journal of Operational Research, 210(3):624–634, 2011\.