Exact enumeration of local minima for kmedoids clustering in a 2D Pareto Front

Nicolas Dupin (1, 2)

1 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
2 Université Paris-Saclay

K-medoids clustering is solvable by dynamic programming in O(N 3) time for a 2D Pareto Front (PF). A key element is a interval clustering optimality. This paper proves this property holds also for local minima for k-medoids. It allows to enumerate the local minima of k-medoids with the same complexity than the computation of global optima for k=2 ou k=3. A pseudo-polynomial enumeration scheme is designed, for small values of k. This allows to understand results obtained by local search approaches in a 2D PF.

Keywords: Local minimums; k-medoids; clustering; Pareto Front

Domains: Computer Science [cs]; Computer Science [cs]; Operations Research [cs.RO]

Nicolas Dupin. Exact enumeration of local minima for kmedoids clustering in a 2D Pareto Front. HUGO 2022 - XV. Workshop on Global Optimization, Sep 2022, Szeged, Hungary. ⟨hal-03695180⟩