This is an announcement for the paper "Randomized rounding for the largest $j$-simplex problem" by Aleksandar Nikolov.

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{R}^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 $\mathsf{NP}$-hard to approximate within a factor of $2^{cj}$ for some constant $c$. Our algorithm also approximates the problem of finding the largest determinant principal $j\times j$ submatrix of a rank $d$ positive semidefinite matrix, with approximation ratio $e^{j + o(j)}$. We achieve our approximation by rounding solutions to a generlization of the $D$-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid probelm. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.

Archive classification: cs.CG cs.DS math.FA

Submitted from: anikolov@cs.rutgers.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1412.0036

or

http://arXiv.org/abs/1412.0036