New Best-Known Max-Cut Solution for the G63 Instance in the G-Set Benchmark
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_ | 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 |