Answers are grounded in this paper and cite their sources.
Develops an approximation algorithm for maximizing determinants in matroid constraints, suggesting significant improvements.
Given a set of vectors v1, ... , 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 T ) 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+ε) d -approximation for a uniform matroid of rank k ≥ d+[d/(ε)] [30], 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)) d3 -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 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.
No takes yet. Share an insight, caveat, or question.
Madan et al. (2020) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: