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

Vilmar Jefté Rodrigues de Sousa (), Miguel F. Anjos and Sébastien Le Digabel
Additional contact information
Vilmar Jefté Rodrigues de Sousa: Polytechnique Montréal
Miguel F. Anjos: Polytechnique Montréal
Sébastien Le Digabel: Polytechnique Montréal

Annals of Operations Research, 2018, vol. 265, issue 1, No 2, 5-27

Abstract: 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 \in \{3,4,5,7\} $$ k ∈ { 3 , 4 , 5 , 7 } . Our computational results suggest that the bicycle wheel and wheel are the strongest inequalities for $$ k=3 $$ k = 3 , and that for $$ k \in \{4,5,7\} $$ 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.

Keywords: Maximum k-cut; Graph partitioning; Semidefinite programming; Computational study; 65K05; 90C22; 90C35 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2448-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:265:y:2018:i:1:d:10.1007_s10479-017-2448-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2448-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().