Maximum Polyhedron Volume in Given $n$ Points

Question

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 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)

Answer 1

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 and SODA 2015. (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).