SAULPIC David

Docteur
Équipe : RO
Date de départ : 30/09/2022
https://www.normalesup.org/~saulpic/
https://www.normalesup.org/~saulpic/

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é

Date de départ : 30/09/2022

Publications 2019-2022

Mentions légales
Carte du site