Publications of Giovanni Rinaldi

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Rinaldi G., in the category IASI Research Reports (or show them all):


IASI Research Report n. 10-25  (Previous    Next)  

Palagi L., Piccialli V., Rendl F., Giovanni Rinaldi, Wiegele A.

Computational approaches to Max-Cut

ABSTRACT
This chapter focuses on the impact that the advances in SDP algorithms have on the compu- tation of good/optimal solutions of the Max-Cut problem. Being Max-Cut NP-hard, the computation of good upper and lower bounds is the kernel of any algorithm for computing good/optimal solutions. SDP relaxations have shown to be particularly successful in the computation of both these bounds. In particular, the Goemans- Williamson algorithm of 1995, that quite substantially contributed to widen the interest for SDP based techniques, plays a fundamental role not only for Max-Cut but also for some related problems. Some of them are shortly described here like, in particular, Max-k-Cut, Coloring and Ordering problems. The main methods available for solving the basic SDP problem are surveyed such as the interior-point methods, the spectral bundle method and, with some emphasis, a recent class of effective non-linear programming based methods. A computational section concludes the chapter, with a comparison of the performances of the main methods described in the previous sections. This article will be published as Chapter 27 of M.F. Anjos and J.B. Lasserre (eds.), Hand- book on Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, Springer. Forthcoming.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -