Optimization Online


Randomized heuristics for the MAX-CUT problem

P. Festa (paola.festa***at***unina.it)
P. M. Pardalos (pardalos***at***ufl.edu)
M. G. C. Resende (mgcr***at***research.att.com)
C. C. Ribeiro (celso***at***inf.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society