Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Ali Civril, Malik Magdon-Ismail

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$ suc…