Maximizing Determinants under Matroid Constraints

Given a set of vectors $\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\in \mathbb{R}^{d}$ and a matroid $\mathcal{M}=([n], \mathcal{I})$, we study the problem of finding a basis $S$ of $\mathcal{M}$ such that $\det(\sum\nolimits_{i\in S}\mathbf{v}_{i}\mathbf{v}_{i}^{\top})$ 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$ [8] and a $(1+\epsilon)^{d}$ -approximation for a uniform matroid of rank $k \geq d+\frac{d}{\epsilon}$ [30], where the rank $k\geq 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\gg 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 new randomized rounding algorithm that crucially exploits the sparsity of solutions to the convex program. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [8], [4] and show new relationships between different convex programs [33], [6] studied for the problem. 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$.

Authors

• Vivek Madan
• Aleksandar Nikolov
• Mohit Singh
• Uthaipon Tao Tantipongpipat

Keywords

• Approximation algorithms
• Partitioning algorithms
• Resource management
• Estimation
• Eigenvalues and eigenfunctions
• Optimization
• Programming
• Matroid Constraint
• Sparsity
• Efficient Algorithm
• Estimation Algorithm
• Dimensional Vector
• Convex Optimization
• Fractional Value
• Sparse Solution
• Fractional Solution
• Optimization Problem
• Linear Function
• Linear Programming
• Feasible Solution
• Value Of Solution
• Structural Inequalities
• Linear Inequalities
• Probability 1
• General Position
• Polynomial-time Algorithm
• Previous Algorithms
• Convex Relaxation
• Infimum
• Network Design Problem
• General Constraints
• Random Solution
• KKT Conditions
• Matroids
• Determinant