Exponential inapproximability of selecting a maximum volume sub-matrix

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

zbMATH Keywords

volumecomplexitymatricesinapproximability

Mathematics Subject Classification ID

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