On the complexity of approximating extremal determinants in matrices (Q1346597)

The author shows that for any polynomial \(p = \text{poly} (d,n)\) in the dimension of a \(d \times n\) matrix \(A\), the problem of approximating \(\delta (A) = \min \{| \text{det} B | : B \in {\mathcal B}\}\), where \({\mathcal B}\) is the set of all nondegenerate \(d \times d\) submatrices (bases) of \(A\), within factor \(2^ P\) is NP-hard. Using NP-hard it is shown whether a set of \(n\) rational points in \(d\) dimensions is affinely or linearly degenerate. Finally, an algorithm for approximating \(\Delta (A) = \max \{| \text{det} B | : B \in {\mathcal B}\}\) within a factor of \([1 + \varepsilon d]^{({d-1 \over 2})}\) in \(O(nd^ 2 (\varepsilon^{-1} + \log d + \log \log n))\) arithmetic operations and comparison over the reals is given also.