Randomized heuristics for the MAX-CUT problem

P. Festa (paola.festaunina.it)
P. M. Pardalos (pardalosufl.edu)
M. G. C. Resende (mgcrresearch.att.com)
C. C. Ribeiro (celsoinf.puc-rio.br)

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 paper, a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS), and a path-relinking (PR) intensification heuristic for MAX-CUT are proposed and tested. New hybrid heuristics that combine GRASP, VNS, and PR are also proposed and tested. Computational results indicate that these randomized heuristics find near-optimal solutions. On a set of standard test problems, new best known solutions were produced for many of the instances.

Keywords: MAX-CUT, GRASP, Variable neighborhood search, Path-relinking, Metaheuristic

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report June 2002

Download: [PDF]

Entry Submitted: 06/24/2002
Entry Accepted: 06/25/2002
Entry Last Modified: 06/24/2002

Modify/Update this entry