N&O lecture: Aleksandar Nikolov (Toronto)

If you are interested you are most welcome to attend this N&O lecture. The title is: Maximizing Determinants under Partition Constraints

Abstract:  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 type of problem appears in diverse areas including determinantal point processes in machine learning, experimental design, geographical placement problem, discrepancy theory and computational geometry. Our main result is to give a geometric concave program for the problem which approximates the optimum value within a factor of exp(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 in the context of estimating the permanent of a doubly stochastic matrix.

Joint work with Mohit Singh