Skip to main navigation
Skip to Content
Computer Science
University of Toronto
Quercus
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar: Mar 6
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar: Mar 6
Event date: Friday, March 06, 2015, at 11:10 AM
Location: GB221
Speaker: Aleksandar Nikolov, Microsoft Research
Title: Randomized Rounding for the Largest j-Simplex Problem
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 a 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 for this problem 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.