CS Events
SeminarRandomized Rounding for the Largest j-Simplex Problem |
|
||
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
Bio
NULL
Location : CoRE A(Room 301)
Committee:
Swastik Kopparty and Shubhangi Saraf
Event Type: Seminar
:
Organization:
Microsoft Research/University of Toronto