Skip to content Skip to navigation
Seminar
2/11/2015 11:00 am
CoRE A(Room 301)

Randomized Rounding for the Largest j-Simplex Problem

Alex Nikolov, Microsoft Research/University of Toronto

Organizer(s): Swastik Kopparty and Shubhangi Saraf

Abstract

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.