k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front

Nicolas Dupin, Frank Nielsen, El‐Ghazali Talbi

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.

Dominance relations in a 2D plane. A Pareto front consists of non-dominated points (like O relative to B and C).

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.

A discrete 2D Pareto front showing the natural ordering of solutions x1 through x15.

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

Abstract

This paper examines a common extension of k-medoids and k-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.
BibTeX
@misc{dupin2018k,
  author = {Nicolas Dupin and Frank Nielsen and El‐Ghazali Talbi},
  title = {{k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front}},
  year = {2018},
  eprint = {1806.02098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.02098},
}
Figure