CS Events Monthly View

Seminar

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

Bio

NULL

Location : CoRE A(Room 301)

Committee

Swastik Kopparty and Shubhangi Saraf

Event Type: Seminar

Abstract: 

Organization

Microsoft Research/University of Toronto