# Randomized Rounding for the Largest Simplex Problem

arXiv: https://arxiv.org/abs/1412.0036 · HTML: https://mlsanity.com/paper/1412.0036/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2014.

## Built on by (most cited first, 10 of 10)

- [Pareto Front-Diverse Batch Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2406.08799/) (2024)
- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)
- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)
- [Composable Coresets for Determinant Maximization: Greedy is Almost Optimal](https://mlsanity.com/paper/2309.15286/) (2023)
- [Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection](https://mlsanity.com/paper/2606.19411/) (2026)
- [Fair Multi-View Determinantal Coresets via Adaptive NEPv](https://mlsanity.com/paper/2608.18181/) (2026)

## Abstract (arXiv)

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 mathbbQd. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of ej/2 + o(j). The problem is known to be NP-hard to approximate within a factor of cj for some constant c > 1. Our algorithm also gives a factor ej + o(j) approximation for the problem of finding the principal j× j submatrix of a rank d positive semidefinite matrix with the largest determinant. 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. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.