Share Email Print
cover

Proceedings Paper

Simulated annealing approach to the max cut problem
Author(s): Sandip Sen
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 23 March 1993
PDF: 6 pages
Proc. SPIE 1963, Applications of Artificial Intelligence 1993: Knowledge-Based Systems in Aerospace and Industry, (23 March 1993); doi: 10.1117/12.141755
Show Author Affiliations
Sandip Sen, Univ. of Michigan (United States)


Published in SPIE Proceedings Vol. 1963:
Applications of Artificial Intelligence 1993: Knowledge-Based Systems in Aerospace and Industry
Usama M. Fayyad; Ramasamy Uthurusamy, Editor(s)

© SPIE. Terms of Use
Back to Top