Georgia Institute of Technology College of Sciences

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics, convex geometry, fair allocations, combinatorics, spectral graph theory, network design, and random processes. In an instance of a determinant maximization problem, we are given a collection of vectors $U = {v_1, \ldots, v_n}$ in $d$ dimensions, and a goal is to pick a subset $S$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_i v_i^T$. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this talk, we give a polynomial-time deterministic algorithm that returns an $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. Our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improves any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the determinant function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

This talk is based on joint work with Adam Brown, Madhusudhan Pittu, Mohit Singh, and Prasad Tetali.