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; P. M., Pardalos; M. G. C., Resende; C. C., Ribeiro. - 1:(2001), pp. 371-376. (Intervento presentato al convegno Fourth Metaheuristics International Conference (MIC2001) tenutosi a Porto, Portogallo nel 16-20 luglio 2001).
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.
