On the complexity of approximating extremal determinants in matrices
type: Item
instance of: scholarly article
title: On the complexity of approximating extremal determinants in matrices
zbMATH Open document ID: 0819.65085
author: Leonid G. Khachiyan
published in: Journal of Complexity
publication date: 1995-04-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 740999
zbMATH Keywords: complexity
zbMATH Keywords: extremal determinants in matrices
zbMATH Keywords: NP-hard
zbMATH Keywords: algorithm
reviewed by: Prem Narain
MaRDI profile type: MaRDI publication profile
full work available at URL: jcom.1995.1005
OpenAlex ID: W2005482089
DOI: 10.1006/JCOM.1995.1005
Recommended article: On largest volume simplices and sub-determinants
Recommended article: The computational complexity of some problems of linear algebra
Recommended article: The (Non)enumerability of the determinant and the rank
Recommended article: Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
Recommended article: On selecting a maximum volume sub-matrix of a matrix and related problems
description: scientific article; zbMATH DE number 740999