Exponential inapproximability of selecting a maximum volume sub-matrix
From MaRDI portal
Publication:1939669
DOI10.1007/s00453-011-9582-6zbMath1259.68086arXiv1006.4349OpenAlexW1826690079MaRDI QIDQ1939669
Ali Çivril, Malik Magdon-Ismail
Publication date: 5 March 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1006.4349
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Column subset selection problem is UG-hard ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Polynomial time \(\rho\)-locally maximum volume search ⋮ Matrices with Hierarchical Low-Rank Structures ⋮ Computing approximate Fekete points by QR factorizations of Vandermonde matrices ⋮ Optimal Interpolation and Compatible Relaxation in Classical Algebraic Multigrid ⋮ Linear-time CUR approximation of BEM matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rang revealing QR factorizations
- Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
- Subset selection for matrices
- On selecting a maximum volume sub-matrix of a matrix and related problems
- Pseudo-skeleton approximations by matrices of maximal volume
- Polynomial-time approximation of largest simplices in \(V\)-polytopes.
- On the existence and computation of rank-revealing LU factorizations
- Largest \(j\)-simplices in \(n\)-polytopes
- Bounds on singular values revealed by QR factorizations
- On the complexity of approximating \(k\)-set packing
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Probabilistic checking of proofs
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- On Rank-Revealing Factorisations
- Low‐rank revealing QR factorizations
- A Parallel Repetition Theorem
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Near Optimal Column-Based Matrix Reconstruction
This page was built for publication: Exponential inapproximability of selecting a maximum volume sub-matrix
