CS Events Monthly View


Randomized Rounding for the Largest j-Simplex Problem


Download as iCal file

Wednesday, February 11, 2015, 11:00am


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. This is a natural problem with long history in computational geometry, and falls in the class of problems of approximating an arbitrary body with a simpler one. We give a deterministic approximation algorithm 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. 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)}. This latter problem has connections with discrepancy theory and low-rank matrix approximation. 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.

Speaker: Alex Nikolov



Location : CoRE A(Room 301)


Swastik Kopparty and Shubhangi Saraf

Event Type: Seminar



Microsoft Research/University of Toronto