Randomized Rounding for the Largest j-Simplex Problem
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.
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Alexander (Sasho) Nikolov
- Affiliation:
- Microsoft Research
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-