Direction de recherche : Christoph DÜRR
Co-encadrement : COHEN-ADDAD Vincent

Algorithmes d'Approximation et Sketches Pour les Problèmes de Clustering

Cette thèse présente des contributions à l'étude théorique des problèmes de clustering. Le vaste objectif de ces problèmes est de partitionner un ensemble de données en groupes, telles que les données d'un même groupe soient similaires. Les problèmes des k-médianes et des k-moyennes sont des façons habituelles de modéliser formellement ce problème, sur lesquelles nous nous concentrons dans cette thèse.

Dans la première partie, nous présentons un schéma d'approximation en temps linéaire quand l'entrée est dans un espace Euclidien de dimension constante (ou, plus généralement, de doubling dimension constante), i.e., un algorithme très rapide qui calcule une approximation très précise de la solution optimale. Nous étendons les techniques utilisées pour traiter le problème du point de vue de la confidentialité différentielle.

Dans la seconde partie, nous cherchons à calculer des représentations simplifiées de l'entrée, qui préservent la structure du problème: nous introduisons plusieurs techniques pour réduire le nombre de données, tout en s'assurant que résoudre le problème après la réduction soit presque équivalent à le résoudre sur l'ensemble initial. Nous montrons aussi que dans plusieurs cas, nos techniques sont optimales.

Dans le cas particulier des espaces Euclidiens, une autre façon de simplifier l'entrée est de réduire la dimension (en préservant de la même façon la structure de l'entrée). Nous présentons le premier algorithme déterministe pour atteindre une dimension presque optimale. Finalement, nous utilisons les algorithmes et techniques introduits précédemment pour calculer très rapidement des indicateurs statistiques.

Soutenance : 13/09/2022

Membres du jury :

Robert Krauthgamer, Weizmann Institute [Rapporteur]
Laurent Viennot, INRIA [Rapporteur]
Cristina Bazgan, Université Paris Dauphine
Monika Henzinger, Universität Wien
Chris Schwiegelshohn, Aarhus University
Vincent Cohen-Addad, Google
Christoph Dürr, Sorbonne Université

Publications 2019-2022

• 2022
  • D. Saulpic : “Algorithmes d’Approximation et Sketches Pour les Problèmes de Clustering”, soutenance de thèse, soutenance 13/09/2022, direction de recherche Dürr, Christoph, co-encadrement : Cohen-addad, Vincent (2022)
  • Th. Ehrhard, S. Attias, E. Bampis, V. Cohen‑Addad, B. Escoffier, C. Mathieu, F. Pascual, A. Pass‑Lanneau, D. Saulpic : “Découpage électoral des circonscriptions législatives en France: déséquilibres démographiques et contraintes territoriales”, Revue Française de Science Politique, vol. Vol. 72 (3), pp. 333-364, (Presses de Sciences Po) (2022)
  • V. Cohen‑Addad, A. Epasto, S. Lattanzi, V. Mirrokni, A. Munoz Medina, D. Saulpic, Ch. Schwiegelshohn, S. Vassilvitskii : “Scalable Differentially Private Clustering via Hierarchically Separated Trees”, KDD '22: Proceedings of the 28^th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington DC, United States, pp. 221-230, (ACM), (ISBN: 978-1-4503-9385-0) (2022)
  • V. Cohen‑Addad, F. Mallmann‑Trenn, D. Saulpic : “A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees”, PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, Salerno, Italy, pp. 356-365, (ACM) (2022)
  • V. Cohen‑Addad, F. Mallmann‑Trenn, D. Saulpic : “Community Recovery in the Degree-Heterogeneous Stochastic Block Model”, Proceedings of Machine Learning Research, vol. 178, Londres, United Kingdom, pp. 1662-1692, (PMLR) (2022)
  • V. Cohen‑Addad, K. Larsen, D. Saulpic, Ch. Schwiegelshohn : “Towards Optimal Lower Bounds for k-median and k-means Coresets”, Proceedings of the 54^th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Rome, Italy, pp. 1038-1051, (Association for Computing Machinery), (ISBN: 9781450392648) (2022)
  • V. Cohen‑Addad, A. Gupta, L. Hu, H. Oh, D. Saulpic : “An Improved Local Search Algorithm for k-Median”, ACM-SIAM Symposium on Discrete Algorithms (SODA22), Alexandria (virtual event), VA, United States, pp. 1556-1612, (Society for Industrial and Applied Mathematics), (ISBN: 978-1-61197-707-3) (2022)
• 2021
  • V. Cohen‑Addad, A. Feldmann, D. Saulpic : “Near-linear Time Approximation Schemes for Clustering in Doubling Metrics”, Journal of the ACM (JACM), vol. 68 (6), pp. 1-34, (Association for Computing Machinery) (2021)
  • A. Feldmann, D. Saulpic : “Polynomial time approximation schemes for clustering in low highway dimension graphs”, Journal of Computer and System Sciences, vol. 122, pp. 72-93, (Elsevier) (2021)
  • V. Cohen‑Addad, D. Saulpic, Ch. Schwiegelshohn : “A new coreset framework for clustering”, STOC 2021: Proceedings of the 53^rd Annual ACM SIGACT Symposium on Theory of Computing, Rome ( Virtual ), Italy, pp. 169-182, (ACM) (2021)
  • V. Cohen‑Addad, D. Saulpic, Ch. Schwiegelshohn : “Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces”, Advances in Neural Information Processing Systems, vol. 34, Virtual, France, pp. 21085-21098, (Curran Associates, Inc.), (ISBN: 9781713845393) (2021)
• 2020
  • A. Feldmann, D. Saulpic : “Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs”, 28^th Annual European Symposium on Algorithms (ESA 2020), vol. 173, Leibniz International Proceedings in Informatics (LIPIcs), Pisa, Italy, pp. 46:1-46:22, (Schloss Dagstuhl--Leibniz-Zentrum für Informatik) (2020)
• 2019
  • V. Cohen‑Addad, N. Hjuler, N. Parotsidis, D. Saulpic, Ch. Schwiegelshohn : “Fully Dynamic Consistent Facility Location”, NeurIPS'19 - 33^rd Conference on Neural Information Processing Systems, Vancouver, United States (2019)
  • V. Cohen‑Addad, A. Feldmann, D. Saulpic : “Near-linear time approximations schemes for clustering in doubling metrics”, FOCS'19, Baltimore, United States (2019)