Fetching the paper…

Reading the bibliography…

2015

Solving maximum cut problems by simulated annealing

Myklebust, Tor G. J.

Original
PDF
Post on X

Understand

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.

Solving maximum cut problems by simulated annealing · Around

Built on

Reducibility among combinatorial problems
Richard M. Karp · 1972
Earlier work this paper cites.
Optimization by simulated annealing
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi · 1983
Earlier work this paper cites.
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
V. Černý · 1985
Earlier work this paper cites.
Optimization by simulated annealing: An experimental evaluation. part i, graph partitioning
David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon · 1989
Earlier work this paper cites.

Similar

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X. Goemans and David P. Williamson · 1995
Cited alongside, same era.
A spectral bundle method for semidefinite programming
Christoph Helmberg and Franz Rendl · 2000
Cited alongside, same era.
Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
Samuel Burer, Renato D. C. Monteiro, and Yin Zhang · 2001
Cited alongside, same era.
Some optimal inapproximability results
Johan Håstad · 2001
Cited alongside, same era.

Then

Randomized heuristics for the MAX-CUT problem
Paola Festa, Panos M. Pardalos, Mauricio G.C. Resende, and Celso C. Ribeiro · 2002
Later among the works it cites.
Optimal inapproximability results for max-cut and other 2-variable csps?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Later among the works it cites.
Advanced scatter search for the max-cut problem
Rafael Martí, Abraham Duarte, and Manuel Laguna · 2009
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…