On the complexity of approximating extremal determinants in matrices
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.
- On largest volume simplices and sub-determinants
- The computational complexity of some problems of linear algebra
- The (Non)enumerability of the determinant and the rank
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- On selecting a maximum volume sub-matrix of a matrix and related problems
- On extremal behaviors of Murty's least index method
- A primal-dual interior point method whose running time depends only on the constraint matrix
- On the hardness of approximating the permanent of structured matrices
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- \(O(n\log^ 2n)\) determinant computation of a Toeplitz matrix and fast variance estimation
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Uniform excess frames in Hilbert spaces
- On the computational complexity of the secure state-reconstruction problem
- LWE with side information: attacks and concrete security estimation
- Sampling-based dimension reduction for subspace approximation with outliers
- Supersaturated designs with the maximum number of factors for a given resolution-rank
- Phase retrieval from very few measurements
- On the fraction of matrices with maximal additive complexity
- Subdeterminant maximization via nonconvex relaxations and anti-concentration
- On the parameterized complexity of \textsc{Girth} and \textsc{Connectivity} problems on linear matroids
- Sum-of-squares optimization without semidefinite programming
- On the tractability of some natural packing, covering and partitioning problems
- The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
- Deterministic APSP, Orthogonal Vectors, and More
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- scientific article; zbMATH DE number 7758358 (Why is no real title available?)
- Optimal resilient sensor placement problem for secure state estimation
- Undirected determinant and its complexity
- An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
- Cardinality minimization, constraints, and regularization: a survey
- Relating code equivalence to other isomorphism problems
- Scientific contributions of Leo Khachiyan (a short overview)
This page was built for publication: On the complexity of approximating extremal determinants in matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346597)
