Randomized Rounding for the Largest Simplex Problem

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 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 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 x 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.

Authors

• Aleksandar Nikolov

Keywords

• approximation algorithms
• computational geometry
• convex optimization
• discrepancy theory