Montag, 04. Dezember 2017, 16:45 - 17:45 iCal

ISOR Colloquium

"The Max-Cut problem: exact methods and heuristics based on quantum techniques"

Speaker: Giovanni Rinaldi (IASI-CNR, Rome)

Sky Lounge, 12th Floor
Oskar-Morgenstern-Platz 1, 1090 Wien


The Max-Cut problem is the one of finding a maximum weight cut in a weighted graph. Because of the its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. Very recently the problem has received a lot of attention since a dedicated hardware, based on quantum annealing, has been realized that yields good solution in amazingly short times for some particular instances (the Chimera graphs). We review some of the exact optimization algorithms today available and how they behave compared to the new quantum approach.

Zur Webseite der Veranstaltung


Institut für Statistik und Operations Research


Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651