Finding a maximum cut is a fundamental task in many computational settings, with a central application in wireless networks. Surprisingly, Max-Cut 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 LOCAL or 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 e > 0, we develop randomized approximation algorithms achieving a ratio of (1 - ε) to the optimum for Max-Cut on bipartite graphs in the CONGEST model, and on general graphs in the 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 Computing 44:1384-1402, 2015) for maximizing an unconstrained (non-monotone) submodular function, which may be of independent interest.
展开▼
