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

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