Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2510.21105 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909867264966656 |
|---|---|
| author | Khan, Nikhat Shukla, Nikhil |
| author_facet | Khan, Nikhat Shukla, Nikhil |
| contents | For over two decades, the G-set benchmark has remained a cornerstone challenge for combinatorial optimization solvers. Remarkably, it continues to yield new best-known solutions even to the present day. Here, we report a new best-known Max-Cut of 27,047 for the 7000-node G63 instance-one of the two instances in the benchmark with the largest number of edges. This result is achieved using an optimized Population Annealing Monte Carlo framework, augmented with adaptive control of stochasticity and the periodic introduction of non-local moves, and accelerated on a GPU platform. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21105 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Best-Known Max-Cut Solution for the G63 Instance in the G-Set Benchmark Khan, Nikhat Shukla, Nikhil Mathematical Physics For over two decades, the G-set benchmark has remained a cornerstone challenge for combinatorial optimization solvers. Remarkably, it continues to yield new best-known solutions even to the present day. Here, we report a new best-known Max-Cut of 27,047 for the 7000-node G63 instance-one of the two instances in the benchmark with the largest number of edges. This result is achieved using an optimized Population Annealing Monte Carlo framework, augmented with adaptive control of stochasticity and the periodic introduction of non-local moves, and accelerated on a GPU platform. |
| title | New Best-Known Max-Cut Solution for the G63 Instance in the G-Set Benchmark |
| topic | Mathematical Physics |
| url | https://arxiv.org/abs/2510.21105 |