On selecting a maximum volume sub-matrix of a matrix and related problems (Q1034598)

Given a real \(m\times n\) matrix, the authors consider the problem of selecting a subset of its columns such that its elements are as linearly independent as possible. The notion is important in low-rank approximations of matrices and rank revealing QR factorizations which have been investigated in the linear algebra community and can be quantified in a few different ways. In the present paper, from a complexity theoretic point of view, the authors propose four related problems. They establish the NP-hardness of these problems and they further show that they do not admit PTAS.