Abstract
This paper examines a common extension of k-medoids and p-median clustering in the case of a two-dimensional Pareto front, as generated by bi-objective optimization approaches. A characterization of optimal clusters is provided, which allows to solve the optimization problems to optimality in polynomial time using a common dynamic programming algorithm. More precisely, having $N$ points to cluster in $K$ subsets, the complexity of the algorithm is proven in $O(N^3)$ time and $O(K.N)$ memory space when $K\geqslant 3$, cases $K=2$ having a time complexity in $O(N^2)$. Furthermore, speeding-up the dynamic programming algorithm is possible avoiding useless computations, for a practical speed-up without improving the complexity. Parallelization issues are also discussed, to speed-up the algorithm in practice.
Introduction
In Multi-Objective Optimization (MOO), decision-makers often deal with a Pareto front—a set of solutions where no objective can be improved without sacrificing another. As these fronts can contain thousands of points, clustering is frequently employed to select a small set of $K$ representative solutions. However, robust methods like k-medoids and p-median clustering are generally NP-hard in 2D space, leading practitioners to rely on heuristics like Lloyd’s algorithm, which lack optimality guarantees.
This research demonstrates that the specific geometric structure of a 2D Pareto front allows these problems to be solved to global optimality in polynomial time. By leveraging the inherent properties of non-dominated sets, the authors transform a computationally intractable task into a manageable one for bi-objective optimization.
Methodology
The fundamental insight of this work is that points on a 2D Pareto front possess a total order. Sorting points by one objective automatically sorts them in reverse order by the second objective. This structural constraint collapses the search space significantly.
Interval Clustering and Dynamic Programming
The authors prove that for a 2D Pareto front, any optimal cluster must be a contiguous interval of points from the sorted sequence. This reduces the search space from an exponential number of groupings to a manageable number of sequence partitions. By introducing a generic cost function with parameter $\alpha$ (where $\alpha=1$ corresponds to p-median and $\alpha=2$ to k-medoids), the authors formulate a unified Dynamic Programming (DP) approach based on Bellman equations. The algorithm builds a table of optimal sub-solutions to find the global optimum for $K$ clusters.
Results
The proposed DP algorithm achieves a time complexity of $O(N^3)$ and $O(KN)$ memory space for $K \ge 3$. For the specific case of $K=2$, the complexity is further reduced to $O(N^2)$. Unlike heuristic methods such as Partitioning Around Medoids (PAM), this approach guarantees the global minimum cost. Additionally, the authors identify that if the Pareto front is strictly convex or concave, the complexity can drop to $O(N \log N)$. Practical speedups are also introduced through stopping criteria that prune unnecessary DP table computations without affecting the theoretical worst-case complexity.
Discussion
While the $O(N^3)$ complexity is a significant theoretical breakthrough, the authors note that these results do not extend to 3D Pareto fronts. In three dimensions, the total order property fails, and the problem returns to being NP-hard. Future work may involve using these exact 2D solutions to initialize heuristics for higher-dimensional problems or exploring approximation algorithms for the 3D case.
Summary updated