Determinant Maximization via Matroid Intersection Algorithms
share
Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics <cit.>, convex geometry <cit.>, fair allocations<cit.>, combinatorics <cit.>, spectral graph theory <cit.>, network design, and random processes <cit.>. In an instance of a determinant maximization problem, we are given a collection of vectors U={v_1,…, v_n}⊂^d, and a goal is to pick a subset S⊆ U of given vectors to maximize the determinant of the matrix ∑_i∈ S v_i v_i^⊤. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S|≤ 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≤ d. This improves previous results that give e^O(r^2)-approximation algorithms relying on e^O(r)-approximate estimation algorithms <cit.> for any r≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. 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 (.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.
READ FULL TEXT