The decision version of the Max-Cut problem was proved to be NP-complete by Karp and remains NP-complete even in the unaligned case. It has found wide application, including VLSI design and statistical physics. In this paper, we study GRASP and VNS heuristics for Max-Cut, together with a combination of the two in a hybrid procedure.
GRASP and VNS for the Max-Cut Problem
FESTA, PAOLA;
2001
Abstract
The decision version of the Max-Cut problem was proved to be NP-complete by Karp and remains NP-complete even in the unaligned case. It has found wide application, including VLSI design and statistical physics. In this paper, we study GRASP and VNS heuristics for Max-Cut, together with a combination of the two in a hybrid procedure.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
