Randomized Rounding for the Largest Simplex Problem

Abstract

The maximum volume $j$-simplex problem asks to compute the $j$-dimensional simplex of maximum volume inside the convex hull of a given set of $n$ points in ${\mathbb{Q}}^d$. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of $e^{j/2+o(j)}$. The problem is known to be $\mathrm{NP}$-hard to approximate within a factor of $c^j$ for some constant $c>1$. Our algorithm also gives a factor $e^{j+o(j)}$ approximation for the problem of finding the principal $j\times j$ submatrix of a rank $d$ positive semidefinite matrix with the largest determinant. We achieve our approximation by rounding solutions to a generalization of the $D$-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid problem. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.