# Solving maximum cut problems by simulated annealing

arXiv: https://arxiv.org/abs/1505.03068 · HTML: https://mlsanity.com/paper/1505.03068/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2015.

## Built on by (most cited first, 4 of 4)

- [HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges](https://mlsanity.com/paper/2506.15196/) (2025)
- [Local Energy Distribution Based Hyperparameter Determination for Stochastic Simulated Annealing](https://mlsanity.com/paper/2304.11839/) (2023)
- [GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling](https://mlsanity.com/paper/2601.14476/) (2026)
- [Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2601.15561/) (2026)

## Abstract (arXiv)

This paper gives a straightforward implementation of simulated annealing for solving maximum cut problems and compares its performance to that of some existing heuristic solvers. The formulation used is classical, dating to a 1989 paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no structure peculiar to the maximum cut problem, but its low per-iteration cost allows it to find better solutions than were previously known for 40 of the 89 standard maximum cut instances tested within a few minutes of computation.