Spring 2019

Constrained Subset Selection Problems under Diversity Measures

Friday, May 3, 2019 9:00 am9:45 am PDT

Add to Calendar


Mohit Singh (Georgia Institute of Technology)

Selecting a diverse subset of items from a collection occurs as a fundamental problem in various applications including selecting representative documents from a corpus, selecting diverse geographical locations for sensor placement and designing most informative experiments. A model is to assign vectors to items and the diversity measure is then defined by spectral functions of natural matrices associated with these vectors. In this talk, I will outline approximation algorithms that aim to optimize these objective measures under combinatorial constraints on the set of items that can be selected. I will also outline the rich connections of the problems to many well-studied problems including counting matchings in graphs, graph sparsification as well as the theory of stable polynomials and positive and negative dependence in probability theory.