Title: On randomized heuristics for the Max-Cut problem


		 	      Paola Festa
	        DMA - University of Napoli FEDERICO II,
	             Compl. MSA, Via Cintia, 80126 
		             Napoli, Italy
		         paola.festa@unina.it
	        http://www.docenti.unina.it/paola.festa


Abstract:
Given an undirected graph with edge weights, the MAX-CUT problem consists in 
finding a partition of the nodes into two subsets, such that the sum of the 
weights of the edges having endpoints in different subsets is maximized.
It is a well-known NP-hard problem with applications in several fields, 
including VLSI design and statistical physics. In this talk, a literature 
review of  approximate and heuristic methods proposed for solving this 
problem will be first presented. Next, it will be given an exhaustive and 
comprehensive  description of meta-heuristic approaches, including a greedy 
randomized adaptive search procedure (GRASP), a variable neighborhood search 
(VNS), a path-relinking (PR) intensification heuristic, and new hybrid 
heuristics that combine GRASP, VNS, and PR.