Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Abstract

Given a matrix $A\in {\mathbb{R}}^{m\times 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 $\delta <1$ and $c>0$ such that this problem is not approximable within $2^{-ck}$ for $k=\delta n$, unless $P=NP$.

14 pages, 2 figures