Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03695180
Contributor : Nicolas Dupin Connect in order to contact the contributor
Submitted on : Tuesday, June 14, 2022 - 3:27:25 PM
Last modification on : Friday, August 5, 2022 - 9:27:29 AM

File

HUGO2022.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03695180, version 1

Citation

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⟩

Share

Metrics

Record views

14

Files downloads

7