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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/185455
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact