Maximizing Determinants under Matroid Constraints

Given a set of vectors v 1 , . . . , v n ∈ R d and a matroid M = ([n], I), we study the problem of finding a basis S of M such that det i∈S v i v ⊤ i is maximized. This problem appears in a diverse set of areas, such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an e 2k -estimation for any matroid of rank k [AGV18] and a (1 + ǫ) d -approximation for a uniform matroid of rank k ≥ d + d ǫ [MSTX19], where the rank k ≥ d denotes the desired size of the optimal set. Our main result is a new approximation algorithm for the general problem with an approximation guarantee that depends only on the dimension d of the vectors, and not on the size k of the output set. In particular, we show an (O(d)) d -estimation and an (O(d)) d 3 -approximation for any matroid, giving a significant improvement over prior work when k ≫ d.

Our result relies on showing that there exists an optimal solution to a convex programming relaxation for the problem which has sparse support ; in particular, no more than O(d 2 ) variables of the solution have fractional values. The sparsity results rely on the interplay between the first order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a randomized rounding algorithm that, given a sparse fractional solution to the convex program, returns a feasible integral solution to the original problem. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [AGV18, ALGV19] and show new relationships between different convex programs [NS16, AG17] studied for the problem. We remark that sparsity is crucial to the algorithm and that all previous approaches will necessarily fail to achieve such an improved guarantee. Finally, we show how to use the estimation algorithm to give an efficient deterministic approximation algorithm. Once again, the algorithm crucially relies on sparsity of the fractional solution to guarantee that the approximation factor depends solely on the dimension d.

• Amazon.