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:
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$
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:
- 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$.
- 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)