Daniel Aloise et Claudio Contardo
Article de revue (2018)
Document en libre accès dans PolyPublie |
|
Libre accès au plein texte de ce document Version finale avant publication Conditions d'utilisation: Tous droits réservés Télécharger (209kB) |
Abstract
We consider the problem of clustering a set of points so as to minimize the maximum intra-cluster dissimilarity, which is strongly NP-hard. Exact algorithms for this problem can handle datasets containing up to a few thousand observations, largely insufficient for the nowadays needs. The most popular heuristic for this problem, the complete-linkage hierarchical algorithm, provides feasible solutions that are usually far from optimal. We introduce a sampling-based exact algorithm aimed at solving large-sized datasets. The algorithm alternates between the solution of an exact procedure on a small sample of points, and a heuristic procedure to prove the optimality of the current solution. Our computational experience shows that our algorithm is capable of solving to optimality problems containing more than 500,000 observations within moderate time limits, this is two orders of magnitude larger than the limits of previous exact methods.
Mots clés
Clustering ; Diameter ; Large-scale optimization
Sujet(s): |
2700 Technologie de l'information > 2700 Technologie de l'information 2700 Technologie de l'information > 2713 Algorithmes |
---|---|
Département: | Département de génie informatique et génie logiciel |
Organismes subventionnaires: | Fonds de recherche Québec - Nature et technologies (FRQNT), CRSNG / NSERC |
Numéro de subvention: | 181909, 435824-2013, 2017-05617 |
URL de PolyPublie: | https://publications.polymtl.ca/3251/ |
Titre de la revue: | Journal of Global Optimization (vol. 71, no 3) |
Maison d'édition: | Springer |
DOI: | 10.1007/s10898-018-0634-1 |
URL officielle: | https://doi.org/10.1007/s10898-018-0634-1 |
Date du dépôt: | 05 sept. 2018 16:39 |
Dernière modification: | 10 avr. 2024 23:35 |
Citer en APA 7: | Aloise, D., & Contardo, C. (2018). A sampling-based exact algorithm for the solution of the minimax diameter clustering problem. Journal of Global Optimization, 71(3), 613-630. https://doi.org/10.1007/s10898-018-0634-1 |
---|---|
Statistiques
Total des téléchargements à partir de PolyPublie
Téléchargements par année
Provenance des téléchargements
Dimensions