Shudian Zhao: SDP-based bounds for k-partitioning via ADMM methods

Abstract: In this presentation, we investigate the quality of semidefinite relaxations strengthened by nonnegativity inequalities and polyhedral cuts for the NP-hard k-equipartition problem. The k-equipartition problem asks to partition an undirected graph into k disjointed groups equally such that the total weight of edges cut by this partition is minimized. To solve the relaxations, we introduce two variants of the alternating direction method of multipliers (ADMM). Numerical experiments demonstrate that we find high quality bounds with reasonable computational costs even for large benchmark instances with up to 1000 vertices.