23 March 1993 Simulated annealing approach to the max cut problem
Author Affiliations +
In this paper we address the problem of partitioning the nodes of a random graph into two sets, so as to maximize the sum of the weights on the edges connecting nodes belonging to different sets. This problem has important real-life counterparts, but has been proven to be NP-complete. As such, a number of heuristic solution techniques have been proposed in literature to address this problem. We propose a stochastic optimization technique, simulated annealing, to find solutions for the max cut problem. Our experiments verify that good solutions to the problem can be found using this algorithm in a reasonable amount of time.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Sandip Sen, Sandip Sen, } "Simulated annealing approach to the max cut problem", Proc. SPIE 1963, Applications of Artificial Intelligence 1993: Knowledge-Based Systems in Aerospace and Industry, (23 March 1993); doi: 10.1117/12.141755; https://doi.org/10.1117/12.141755

Back to Top