An Improved Approximation Algorithm for the Max-$3$-Section Problem

Abstract

We consider the Max-$3$-Section problem, where we are given an undirected graph $G=(V,E)$ equipped with non-negative edge weights $w:E\to {\mathbb{R}}_{+}$ and the goal is to find a partition of $V$ into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-$3$-Section is closely related to other well-studied graph partitioning problems, e.g., Max-$k$-Cut, Max-$3$-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of $0.795$, that improves upon the previous best known approximation of $0.673$. The requirement of multiple parts that have equal sizes renders Max-$3$-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.