Maximizing determinants under partition constraints

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 the submatrix of L induced by the rows and columns in B is maximized. This problem appears in many areas including determinantal point processes in machine learning, experimental design, geographical placement problems, discrepancy theory and computational geometry to model subset selection problems that incorporate diversity.

Authors

• Aleksandar Nikolov
• Mohit Singh

Keywords

• determinantal point processes
• maximum subdeterminant
• logsubmodular optimization
• approximation algorithms