Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918390692577280 |
|---|---|
| author | Cory-Wright, Ryan Pauphilet, Jean |
| author_facet | Cory-Wright, Ryan Pauphilet, Jean |
| contents | Building on the blueprint from Goemans and Williamson (1995) 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. When optimizing for $m$ orthonormal vectors in dimension $n$, we leverage strong duality and semidefinite complementary slackness to show that our algorithm achieves a $1/3$-approximation ratio. For any $m$ of the form $2^q$ for some integer $q$, we also construct an instance where the performance of our algorithm is exactly $(m+2)/(3m)$, which can be made arbitrarily close to $1/3$ by taking $m \rightarrow + \infty$, hence showing that our analysis is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02942 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization Cory-Wright, Ryan Pauphilet, Jean Optimization and Control Machine Learning Probability Building on the blueprint from Goemans and Williamson (1995) 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. When optimizing for $m$ orthonormal vectors in dimension $n$, we leverage strong duality and semidefinite complementary slackness to show that our algorithm achieves a $1/3$-approximation ratio. For any $m$ of the form $2^q$ for some integer $q$, we also construct an instance where the performance of our algorithm is exactly $(m+2)/(3m)$, which can be made arbitrarily close to $1/3$ by taking $m \rightarrow + \infty$, hence showing that our analysis is tight. |
| title | Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization |
| topic | Optimization and Control Machine Learning Probability |
| url | https://arxiv.org/abs/2501.02942 |