Retour aux activités
Discussion DS4DM autour d'un café

Preserving Diversity When Partitioning: A Geometric Approach


13 mai 2022   11h00 — 12h00

Alfredo Torrico Polytechnique Montréal, Canada

Alfredo Torrico

Séminaire hybrique sur Zoom et dans la salle de séminaire du GERAD.

Diversity plays a crucial role in team formation, representation of minority groups and generally when allocating resources fairly. Given a community composed by individuals of different types, we study the problem of dividing this community such that the global diversity is preserved as much as possible in each subgroup. We consider the diversity metric introduced by Simpson in his influential work that, roughly speaking, corresponds to the inverse of the probability that two individuals are from the same type when taken at random, with replacement. We provide a novel perspective by reinterpreting this quantity in geometric terms. We characterize the instances in which the optimal partition exactly preserves the global diversity in each subgroup. When this is not possible, we provide an efficient polynomial-time algorithm that outputs an optimal partition for the problem with two types. Finally, we discuss further challenges and open questions for the problem that considers more than two types.

Federico Bobbio responsable
Gabriele Dragotto responsable


Séminaire hybride au GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4

Organismes associés

Axe de recherche

Application de recherche