  In an instance of the minimum eigenvalue problem, we are given a collection
of $n$ vectors $v_1,\ldots, v_n \subset {\mathbb{R}^d}$, and the goal is to
pick a subset $B\subseteq [n]$ of given vectors to maximize the minimum
eigenvalue of the matrix $\sum_{i\in B} v_i v_i^{\top} $. Often, additional
combinatorial constraints such as cardinality constraint $\left(|B|\leq
k\right)$ or matroid constraint ($B$ is a basis of a matroid defined on $[n]$)
must be satisfied by the chosen set of vectors. The minimum eigenvalue problem
with matroid constraints models a wide variety of problems including the Santa
Clause problem, the E-design problem, and the constructive Kadison-Singer
problem.
  In this paper, we give a randomized algorithm that finds a set $B\subseteq
[n]$ subject to any matroid constraint whose minimum eigenvalue is at least
$(1-\epsilon)$ times the optimum, with high probability. The running time of
the algorithm is $O\left( n^{O(d\log(d)/\epsilon^2)}\right)$. In particular,
our results give a polynomial time asymptotic scheme when the dimension of the
vectors is constant. Our algorithm uses a convex programming relaxation of the
problem after guessing a rescaling which allows us to apply pipage rounding and
matrix Chernoff inequalities to round to a good solution. The key new component
is a structural lemma which enables us to "guess'' the appropriate rescaling,
which could be of independent interest. Our approach generalizes the
approximation guarantee to monotone, homogeneous functions and as such we can
maximize $\det(\sum_{i\in B} v_i v_i^\top)^{1/d}$, or minimize any norm of the
eigenvalues of the matrix $\left(\sum_{i\in B} v_i v_i^\top\right)^{-1} $, with
the same running time under some mild assumptions. As a byproduct, we also get
a simple algorithm for an algorithmic version of Kadison-Singer problem.
