Randomized heuristics for the Max-Cut problem

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, in...

Full description

Saved in:
Bibliographic Details
Published in:Optimization methods & software 2002-12, Vol.17 (6), p.1033-1058
Main Authors: Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.
Format: Article
Language:English
Subjects:
Grasp
Max-Cut
Metaheuristics
Path-relinkings
Variable Neighborhood Search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 article, 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.
ISSN:1055-6788
1029-4937
DOI:10.1080/1055678021000090033