Burer, Monteiro, and Zhang [2001] proposed a rank-2 relaxation heuristic for MAX-CUT and described a computer code, called circut, that produces better solutions in practice than the randomized algorithm of Goemans and Williamson [1995]. Their heuristic is based on continuous optimization and can be applied for solving any binary quadratic program. In this talk, we discuss on how to add path-relinking to circut as a way to intensify search around high-quality solutions produced by circut.
A randomized multistart rank-2 algorithm for Max-Cut / Festa, Paola. - (2008). (Intervento presentato al convegno XXXIX Annual Conference Italian Operational Research Society - AIRO 2008 tenutosi a Hotel Continental Terme, Ischia (NA), Italia nel 8-11 Settembre 2008).
A randomized multistart rank-2 algorithm for Max-Cut
FESTA, PAOLA
2008
Abstract
Burer, Monteiro, and Zhang [2001] proposed a rank-2 relaxation heuristic for MAX-CUT and described a computer code, called circut, that produces better solutions in practice than the randomized algorithm of Goemans and Williamson [1995]. Their heuristic is based on continuous optimization and can be applied for solving any binary quadratic program. In this talk, we discuss on how to add path-relinking to circut as a way to intensify search around high-quality solutions produced by circut.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
