<p>This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest volume simplices and sub-determinants", <a href="https://arxiv.org/abs/1406.3512" rel="noreferrer">arXiv:1406.3512</a> and <a href="http://dl.acm.org/citation.cfm?id=2722152" rel="noreferrer">SODA 2015</a>. (They talk about the largest volume simplex contained in the convex hull, rather than the one that has the given points as vertices, but it amounts to the same thing since there is always an optimal contained simplex that has the given points as vertices.) They cite earlier hardness results on the same problem by Packer (ref.37 of the arXiv preprint) and Papadimitriou (ref.38).</p>

CC BY-SA 3.0
2017-05-09T03:35:44.310Z
If you only care about NP-hardness rather than hardness of approximation, then the first proof is due to Klee, Gritzmann, and Larman, Largest j-Simplices in n-Polytopes.
Sasho Nikolov
CC BY-SA 3.0
2017-05-09T00:38:31.157Z
2017-05-09T00:38:31.157Z
David Eppstein
<p>Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them maximized (where any $k$ vectors in $v_{i_j}$s should be linear independent, otherwise the volume can simply be $0$).</p>

<p>I know the <strong>Minimizing</strong> version of this problem can be shown to be NP-Hard, e.g. one can reduce the subset sum problem to it as follows:</p>

<ol>
<li><p>For given $n$ distinct reals $a_1,a_2,\cdots, a_{n-1}$, we want to know if there are $k$ numbers in $a_i$s that sum to $\beta$</p></li>
<li><p>Define $v_i=[1,a_i,a_i^2,\cdots,a_i^{k-1}]$ and $v_n=[0,\cdots,0,1,\beta]$, one can show (by Vandermonde matrix) that the problem in $1$ is true iff there are $k$ vectors in $v_i$s are linear dependent</p></li>
</ol>

<blockquote>
  <p>My question is: does the <strong>Maximizing</strong> version of this problem also NP-Hard? or Can one find a polynomial algorithm for it?</p>
</blockquote>

<p>I was trying to find a similar reduction as above, but there seems to be a lot difficulty.</p>

<p><strong>Edit</strong>: Actually, this <a href="http://aiu.edu.tr/staff/ali.civril/max-vol.pdf" rel="nofollow noreferrer">paper</a> provided a rather simple reduction from X3C as follows:</p>

<ol>
<li>let $Q=\{q_1,q_2,\cdots, q_m\}$ and $C=\{c_1,c_2,\cdots, c_n\}$ be an instance of X3C, we want to find $C'\subset C$ such that $c_1'\cap c_2' =\phi$ for all $c_1'\not=c_2'\in C'$ and $\bigcup_{c'\in C'}c'=Q$.</li>
<li>for each $q_i$, define $v_i[j]=1/\sqrt{3}$ if $q_i\in c_j$ and $v_i[j]=0$ otherwise.</li>
</ol>

<p>clearly, the instance in 1 is true iff the maximal volume is 1. (though this approach only gives a hardness result with constant approximate ratio)</p>

<np-hardness><determinant><high-dimensional-geometry>
Maximum Polyhedron Volume in Given $n$ Points
Paul
# Maximum Polyhedron Volume in Given $n$ Points

(Asked by: username_0 on 2017-04-24)

Suppose we are given $n$ points $v\_1,v\_2,\cdots, v\_n\in \mathbb{R}^k$, I want to find $k+1$ points $v\_{i\_1}, v\_{i\_2},\cdots,v\_{i\_{k+1}}$ such that the volume of the convex body spanned by them maximized (where any $k$ vectors in $v\_{i\_j}$s should be linear independent, otherwise the volume can simply be $0$).

I know the **Minimizing** version of this problem can be shown to be NP-Hard, e.g. one can reduce the subset sum problem to it as follows:

1. For given $n$ distinct reals $a\_1,a\_2,\cdots, a\_{n-1}$, we want to know if there are $k$ numbers in $a\_i$s that sum to $\beta$
2. Define $v\_i=[1,a\_i,a\_i^2,\cdots,a\_i^{k-1}]$ and $v\_n=[0,\cdots,0,1,\beta]$, one can show (by Vandermonde matrix) that the problem in $1$ is true iff there are $k$ vectors in $v\_i$s are linear dependent

> My question is: does the **Maximizing** version of this problem also NP-Hard? or Can one find a polynomial algorithm for it?

I was trying to find a similar reduction as above, but there seems to be a lot difficulty.

**Edit**: Actually, this [paper](http://aiu.edu.tr/staff/ali.civril/max-vol.pdf) provided a rather simple reduction from X3C as follows:

1. let $Q=\{q\_1,q\_2,\cdots, q\_m\}$ and $C=\{c\_1,c\_2,\cdots, c\_n\}$ be an instance of X3C, we want to find $C'\subset C$ such that $c\_1'\cap c\_2' =\phi$ for all $c\_1'\not=c\_2'\in C'$ and $\bigcup\_{c'\in C'}c'=Q$.
2. for each $q\_i$, define $v\_i[j]=1/\sqrt{3}$ if $q\_i\in c\_j$ and $v\_i[j]=0$ otherwise.

clearly, the instance in 1 is true iff the maximal volume is 1. (though this approach only gives a hardness result with constant approximate ratio)

**Tags:** np-hardness, determinant, high-dimensional-geometry


---

## 1 answers

### Answer by username_1 on 2017-05-09. Score: 11 | Accepted answer

This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest volume simplices and sub-determinants", [arXiv:1406.3512](https://arxiv.org/abs/1406.3512) and [SODA 2015](http://dl.acm.org/citation.cfm?id=2722152). (They talk about the largest volume simplex contained in the convex hull, rather than the one that has the given points as vertices, but it amounts to the same thing since there is always an optimal contained simplex that has the given points as vertices.) They cite earlier hardness results on the same problem by Packer (ref.37 of the arXiv preprint) and Papadimitriou (ref.38).

> **Comments:**
> **username_2**: If you only care about NP-hardness rather than hardness of approximation, then the first proof is due to Klee, Gritzmann, and Larman, Largest j-Simplices in n-Polytopes.  

---

