- | ||||
|
![]()
|
Randomized heuristics for the MAX-CUT problem
P. Festa (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 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |