Title: Fast Distributed Approximation for Max-Cut,
Abstract: Finding a maximum cut is a fundamental task in many computational settings.
Surprisingly, it has been insufficiently studied in the classic distributed
settings, where vertices communicate by synchronously sending messages to their
neighbors according to the underlying graph, known as the $\mathcal{LOCAL}$ or
$\mathcal{CONGEST}$ models. We amend this by obtaining almost optimal
algorithms for Max-Cut on a wide class of graphs in these models. In
particular, for any $\epsilon > 0$, we develop randomized approximation
algorithms achieving a ratio of $(1-\epsilon)$ to the optimum for Max-Cut on
bipartite graphs in the $\mathcal{CONGEST}$ model, and on general graphs in the
$\mathcal{LOCAL}$ model.
We further present efficient deterministic algorithms, including a
$1/3$-approximation for Max-Dicut in our models, thus improving the best known
(randomized) ratio of $1/4$. Our algorithms make non-trivial use of the greedy
approach of Buchbinder et al. (SIAM Journal on Computing, 2015) for maximizing
an unconstrained (non-monotone) submodular function, which may be of
independent interest.