Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization

ArXi:2501.02942v4 Announce Type: replace-cross Building on the blueprint from Goemans and Williamson for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm.