Given a matrix A∈ℝm×n (n vectors in m dimensions), and a positive integer k
<n, we consider the problem of selecting k column vectors from A such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists δ
<1 and c>0 such that this problem is not approximable within 2−ck for k=δn, unless P=NP.
