Description
Date depot: 15 février 2019
Titre: Approximation Algorithms for Fair and Private Clustering
Directeur de thèse:
Christoph DURR (LIP6)
Encadrant :
Vincent COHEN-ADDAD (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Clustering data according to similarity is a fundamental, routinely-used approach to analyze, classify,
and pre-process big datasets, what is commonly referred to as Big Data1. Given a dataset and the most
important features of the data, a clustering is a partition of the data such that similar data elements are
in the same part. A clustering provides useful information on the data that can be used e.g., to divide
a digital image into distinct regions, identify communities in social networks, classify genes according to
their expression patterns, or solve redistricting problems.
Thus, to design a principled approach for these problems one needs to focus on models of real-world
inputs and on the heuristics that are used in practice, then understand how these heuristics perform on
these inputs and explain their success, and finally design new algorithm that are at least as efficient as
the existing heuristics but ensures fairness and privacy. This is the goal of this thesis.
Doctorant.e: Saulpic David