Improved Approximation Al
Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization
Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization
arXiv:2501.02942v1 Announce Type: cross
Abstract: Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-sample strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, w…