Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2504.07204 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917441150386176 |
|---|---|
| author | Gong, Rui Cifuentes, Diego Toriello, Alejandro |
| author_facet | Gong, Rui Cifuentes, Diego Toriello, Alejandro |
| contents | The Lovász theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect graphs, there is no known rounding method guaranteed to extract a maximum weighted stable set from the SDP solution. In this paper, we develop a novel rounding scheme for the theta function that constructs a value function approximation from the SDP solution and then generates a stable set using dynamic programming. Our method provably recovers a maximum weighted stable set in several sub-classes of perfect graphs, including generalized split graphs, which asymptotically cover almost all perfect graphs. To the best of our knowledge, this is the only known rounding strategy for the theta function that recovers a maximum weighted stable set for large classes of perfect graphs. Our rounding scheme relies on simple linear algebra computations; we only solve one SDP. In contrast, existing methods that leverage the theta function require solving multiple SDPs. Computational experiments show that our method produces good solutions even on imperfect graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07204 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rounding the Lovász Theta Function with a Value Function Approximation Gong, Rui Cifuentes, Diego Toriello, Alejandro Optimization and Control The Lovász theta function is a semidefinite programming (SDP) relaxation for the maximum weighted stable set problem, which is tight for perfect graphs. However, even for perfect graphs, there is no known rounding method guaranteed to extract a maximum weighted stable set from the SDP solution. In this paper, we develop a novel rounding scheme for the theta function that constructs a value function approximation from the SDP solution and then generates a stable set using dynamic programming. Our method provably recovers a maximum weighted stable set in several sub-classes of perfect graphs, including generalized split graphs, which asymptotically cover almost all perfect graphs. To the best of our knowledge, this is the only known rounding strategy for the theta function that recovers a maximum weighted stable set for large classes of perfect graphs. Our rounding scheme relies on simple linear algebra computations; we only solve one SDP. In contrast, existing methods that leverage the theta function require solving multiple SDPs. Computational experiments show that our method produces good solutions even on imperfect graphs. |
| title | Rounding the Lovász Theta Function with a Value Function Approximation |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2504.07204 |