Determinant Maximization via Matroid Intersection Algorithms

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_{1}, \cdots, \ v_{n}\}\subset \mathbb{R}^{d}$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\displaystyle \sum_{i\in S}v_{i}v_{i}^{\text{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 paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. This improves previous results that give $e^{O(r^{2})}$-approximation algorithms relying on $e^{O(r)}$-approximate estimation algorithms [4], [7] –[9] for any r$\leq$d. All previous results use convex relaxations and their relationship to stable polynomials and strongly $\log$-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

Authors

• Adam Brown
• Aditi Laddha
• Madhusudhan Reddy Pittu
• Mohit Singh
• Prasad Tetali

Keywords

• Geometry
• Computer science
• Linear approximation
• Estimation
• Approximation algorithms
• Graph theory
• Random processes
• Matroid Intersection
• Estimation Algorithm
• Network Design
• Diverse Fields
• Problem Instances
• Negative Cycle
• Spectral Graph Theory
• Collection Of Vectors
• Spectral Network
• Value Function
• Efficient Algorithm
• Weight Function
• Objective Value
• Convex Optimization
• Feasible Set
• Diagonal Entries
• Off-diagonal Entries
• Minimum Cycle
• Number Of Arcs
• Computations on discrete structures
• Combinatorial algorithms