# On largest volume simplices and sub-determinants

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2014.

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

- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)
- [Experimental Design Using Interlacing Polynomials](https://mlsanity.com/paper/2410.11390/) (2024)
- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)

## Abstract (arXiv)

We show that the problem of finding the simplex of largest volume in the convex hull of n points in mathbbQd can be approximated with a factor of O(log d)d/2 in polynomial time. This improves upon the previously best known approximation guarantee of d(d-1)/2 by Khachiyan. On the other hand, we show that there exists a constant c>1 such that this problem cannot be approximated with a factor of cd, unless P=NP. % This improves over the 1.09 inapproximability that was previously known. Our hardness result holds even if n = O(d), in which case there exists a bar c,d-approximation algorithm that relies on recent sampling techniques, where bar c is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a d× n matrix.