Giovanni Rinaldi

Giovanni Rinaldi	IASI-CNR, Rome, Italy
Giovanni Rinaldi is a Research Director of the Italian National Research Council (CNR). He received a master degree in System Science at the Engineering School of the University of Rome in 1976. In 1982 he got a tenured position as a researcher at the Institute on System Analysis and Compute Science (IASI) of the CNR, of which is the director from 2014. He directed the same Institute from 1998 to 2009. He was Visiting Professor at the New York University and at the universities of Augsburg, Cologne and Heidelberg. His main research interests are in Combinatorial Optimization, in particular in the study of structural properties of hard problems and in their exploitation to design efficient exact algorithms. His favorite problems are the Traveling Salesman, the Vehicle Routing and The Max-Cut Problem.

IASI-CNR, Rome, Italy

Giovanni Rinaldi is a Research Director of the Italian National Research Council (CNR). He received a master degree in System Science at the Engineering School of the University of Rome in 1976. In 1982 he got a tenured position as a researcher at the Institute on System Analysis and Compute Science (IASI) of the CNR, of which is the director from 2014. He directed the same Institute from 1998 to 2009. He was Visiting Professor at the New York University and at the universities of Augsburg, Cologne and Heidelberg. His main research interests are in Combinatorial Optimization, in particular in the study of structural properties of hard problems and in their exploitation to design efficient exact algorithms. His favorite problems are the Traveling Salesman, the Vehicle Routing and The Max-Cut Problem.

Maximum weight cuts in graphs and extensions
Max-Cut, i.e., the problem of finding a cut of maximum weight in a weighted graph, is one on the most studied and best known hard optimization problems on graphs. Max-Cut is also known to be equivalent to Unconstrained Quadratic Binary Optimization, i.e., to the problem of minimizing a quadratic form in binary variables. Because on 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. We review some of the most successful solution methods proposed for this problem and for some extensions where, instead of a quadratic form, we consider a polynomial of degree higher than two.

Maximum weight cuts in graphs and extensions

Max-Cut, i.e., the problem of finding a cut of maximum weight in a weighted graph, is one on the most studied and best known hard optimization problems on graphs. Max-Cut is also known to be equivalent to Unconstrained Quadratic Binary Optimization, i.e., to the problem of minimizing a quadratic form in binary variables. Because on 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. We review some of the most successful solution methods proposed for this problem and for some extensions where, instead of a quadratic form, we consider a polynomial of degree higher than two.