Maximizing Determinants under Partition Constraints

Aleksandar Nikolov, Mohit Singh

Proceedings of The 48th ACM Symposium on Theory of Computing (STOC) 2016. |

Given a positive semidefinte matrix L whose columns and rows are indexed by a set U, and a partition matroid M = (U, I), we study the problem of selecting a basis B of M such that the determinant of submatrix of L, restricted to rows and columns of B, is maximized. This problem appears in diverse areas including determinantal point processes in machine learning [KT12], experimental design, geographical placement problem [Lee98, KLQ95], discrepancy theory and computational geometry [Nik14]. Our main result is to give a geometric concave program for the problem which approximates the optimum value within a factor of e r+o(r) , where r denotes the rank of the partition matroid M. We bound the integrality gap of the geometric concave program by giving a polynomial time randomized rounding algorithm. To analyze the rounding algorithm, we relate the solution of our algorithm as well the objective value of the relaxation to a certain stable polynomial. To prove the approximation guarantee, we utilize a general inequality about stable polynomials proved by Gurvits [Gur08] in the context of estimating the permanent of a doubly stochastic matrix