### Vilmar Rodrigues de Sousa (Polytechnique MontrĂ©al)

#### Computational study of valid inequalities for the maximum k-cut problem

*Wednesday 10 May 2017 at 15.00, JCMB 6206*

##### Abstract

We consider the maximum k-cut problem that consists in partitioning the vertex
set of a graph into k subsets such that the sum of the weights of edges
joining vertices in different subsets is maximized. We focus on identifying
effective classes of inequalities to tighten the semidefinite programming
relaxation. We carry out an experimental study of four classes of inequalities
from the literature: clique, general clique, wheel and bicycle wheel. We
considered 10 combinations of these classes and tested them on both dense and
sparse instances for k ∈ {3, 4, 5, 7}. Our computational results suggest
that the bicycle wheel and wheel are the strongest inequalities for k = 3,
and that for k ∈ {4, 5, 7} the wheel inequalities are the strongest by
far. Furthermore, we observe an improvement in the performance for all choices
of k when both bicycle wheel and wheel are used, at the cost of 72% more CPU
time on average when compared with using only one of them.

### Seminars by year

*Current*
*2017*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*