Abstract
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 can be modeled as finding the principal submatrix of a given positive semi-definite matrix of largest determinant. Typically, the problem has additional side constraints on the collection of submatrices that can be selected. We design approximation algorithms for the problem with additional partition constraints. Our algorithm relies on efficient polynomial optimization and reveals surprising connections to the problem of counting matchings via the theory of hyperbolic polynomials.
This is joint work with Sasho Nikolov.