Randomized Rounding for the Largest j-Simplex Problem

Опубликовано 21 июня 2016, 23:40

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 d-dimensional space. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of e j/2 + o(j) and runs in time polynomial in d and n. The problem is known to be NP-hard to approximate within a factor of c j for some constant c > 1. Our algorithm also approximates the problem of finding the largest determinant principal j-by-j submatrix of a positive semidefinite matrix, with approximation ratio e j + o(j) . 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.