Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908978382897152 |
|---|---|
| author | Proença, Nathan Benedetto Silva, Marcel K. de Carli Sato, Cristiane M. Tunçel, Levent |
| author_facet | Proença, Nathan Benedetto Silva, Marcel K. de Carli Sato, Cristiane M. Tunçel, Levent |
| contents | We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then simultaneously certify the approximate optimality of a cut and a fractional cut cover. We present several implementations which reliably achieve the celebrated Goemans and Williamson approximation ratio of $α_{\mathrm{GW}} \approx 0.878$ for both optimization problems simultaneously, after $\lceil 128 \ln m \rceil$ samples, a number significantly smaller than the best theoretical bounds.
This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after $\lceil 128 \ln m \rceil$ samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_17661 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach Proença, Nathan Benedetto Silva, Marcel K. de Carli Sato, Cristiane M. Tunçel, Levent Optimization and Control Discrete Mathematics We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then simultaneously certify the approximate optimality of a cut and a fractional cut cover. We present several implementations which reliably achieve the celebrated Goemans and Williamson approximation ratio of $α_{\mathrm{GW}} \approx 0.878$ for both optimization problems simultaneously, after $\lceil 128 \ln m \rceil$ samples, a number significantly smaller than the best theoretical bounds. This is the first experimental work approximating the weighted fractional cut-covering problem, and we deliver robust and repeatable results despite the use of randomized algorithms and floating-point arithmetic. Careful pre-processing of instances and post-processing of numeric results allow for good empirical outcomes with both first-order and second-order SDP solvers. Nearly optimal SDP solutions are suitably perturbed to ensure better probabilistic and numerical behavior. Our experiments deviate from theory by using a linear programming (LP) solver to compute fractional cut covers. For most instances studied, LP solving produces certifiably better results than the theoretical algorithm after $\lceil 128 \ln m \rceil$ samples. All our experiments strictly follow a unified pipeline which explicitly documents all parameters used in each run. |
| title | Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2604.17661 |