Randomized Rounding for the Largest Simplex Problem

2014/11/28 by Nikolov, Aleksandar · 6 citations
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA)

paper · doi:10.48550/arxiv.1412.0036

Abstract

The maximum volume j-simplex problem asks to compute the j-dimensional simplex of maximum volume inside the convex hull of a given set of n points in ℚ^d. We give a deterministic approximation algorithm for this problem which achieves an approximation ratio of e^{j/2 + o(j)}. The problem is known to be NP-hard to approximate within a factor of c^j for some constant c > 1. Our algorithm also gives a factor e^{j + o(j)} approximation for the problem of finding the principal j× j submatrix of a rank d positive semidefinite matrix with the largest determinant. We achieve our approximation by rounding solutions to a generalization of the D-optimal design problem, or, equivalently, the dual of an appropriate smallest enclosing ellipsoid problem. Our arguments give a short and simple proof of a restricted invertibility principle for determinants.

Cited by

• Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
• On the relationship between MESP and 0/1 D-Opt and their upper bounds
• Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy
• Finding a Maximal Determinant Principal Submatrix via Hadamard's Inequality and Conic Relaxations
• Recent Advances in Maximum-Entropy Sampling
• On the Vertices of Delta-modular Polyhedra

Related

• On largest volume simplices and sub-determinants
• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations
• Some problems in asymptotic convex geometry and random matrices motivated by numerical algorithms
• On maximum volume submatrices and cross approximation for symmetric\n semidefinite and diagonally dominant matrices