Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

2010/06/22 by Ali Çivril, Civril, Ali, Malik Magdon‐Ismail +1 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1006.4349

openalex publication_date 2010/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a matrix A ∈ ℝ^{m × n} (n vectors in m dimensions), and a positive integer k < n, we consider the problem of selecting k column vectors from A such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists δ<1 and c>0 such that this problem is not approximable within 2^-ck for k = δn, unless P=NP.

Citations

• Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition

Cited by

• Many (most?) column subset selection criteria are NP hard

Related

• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• On maximum volume submatrices and cross approximation for symmetric\n semidefinite and diagonally dominant matrices
• On largest volume simplices and sub-determinants
• Rectangular maximum volume and projective volume search algorithms
• Many (most?) column subset selection criteria are NP hard