Randomized Rounding for the Largest Simplex Problem

Original · EN

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ᵈ. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of eʲ/² ⁺ ᵒ⁽ʲ⁾. The problem is known to be NP-hard to approximate within a factor of cʲ for some constant c > 1. Our algorithm also gives a factor eʲ ⁺ ᵒ⁽ʲ⁾ approximation for the problem of finding the principal j× 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.