Randomized Rounding for the Largest j-Simplex Problem

  • Alexander (Sasho) Nikolov | Microsoft Research

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 ej/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 cj 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 ej + 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.

Speaker Details

Sasho Nikolov recently received his PhD from the Computer Science Department of Rutgers University and is currently a postdoc with the Theory Group in MSR Redmond. In July 2015 he will join the Department of Computer Science in the University of Toronto. He is broadly interested in theoretical computer science and algorithms, and specifically in discrepancy theory and its applications to computer science, and in computational questions about discrepancy. He has worked on applications of discrepancy theory to approximation algorithms and to differential privacy, and is also interested in convex geometry, and in sublinear and parallel algorithms for massive data.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks