Mohit Singh (Theory Seminar)

Mohit Singh (Georgia Institute of Technology)
Monday, February 13, 2017, 2:00pm


Title: Constrained Subset Selection Problems, Permanents and Inequalities on Stable Polynomials


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. The problem is modeled by maximizing the entropy of the joint distribution of the selected items and, typically, has additional side constraints. We design approximation algorithms for the subset selection problem with additional partition constraints. Our algorithm relies on efficient polynomial optimization and reveals surprising connections to the problem of computing the permanent of a matrix. The crucial ingredient in this connection are inequalities on stable polynomials.

This is joint work with Sasho Nikolov.