Algorithms Seminar

Constrained Subset Selection Problems under Determinantal Measure

Speaker:Mohit Singh
Date: Friday, October 6, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


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. Among the different formulations of the problem in many of these areas, a common occurrence is to use the determinantal measure as a proxy for diversity or information. I will talk about recent works on approximation algorithms for constrained subset selection problems under the determinantal measure. I will also outline the rich connections of the problem 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.


Mohit Singh is an associate professor in the School of Industrial & Systems Engineering at Georgia Institute of Technology, Atlanta. His research interests include discrete optimization, approximation algorithms and convex optimization. His research focuses on optimization problems arising in cloud computing, logistics, network design, and machine learning. Previously, he was a researcher in the theory group at Microsoft Research, Redmond from 2011-2016, an assistant professor at McGill University from 2010-2011 and a post-doctoral researcher at Microsoft Research, New England from 2008-2009. He obtained his Ph.D. from Carnegie Mellon University and his doctoral thesis received the Tucker prize in 2009 given by the Mathematical Optimization Society. He has also received the best paper award for his work on the traveling salesman problem at the Annual Symposium on Foundations of Computer Science (FOCS) 2011.