Fast Distributed Approximation for Max-Cut

DOI10.1007/978-3-319-72751-6_4MaRDI QIDQ5056049zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Rina Levy, Hadas Shachnai

Publication date 9 December 2022

Published in Algorithms for Sensor Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.08496

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Distributed algorithms (68W15)

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 $mathcalLOCAL$ or $mathcalCONGEST$ 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 $mathcalCONGEST$ model, and on general graphs in the $mathcalLOCAL$ 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.

Recommendations

• Local approximation of the maximum cut in regular graphs
• Near-optimal distributed maximum flow (extended abstract)
• Distributed minimum cut approximation
• Near-optimal distributed maximum flow
• Distributed approximate maximum matching in the CONGEST model

Cites work

• scientific article; zbMATH DE number 1833408 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Strong Diameter Network Decomposition
• Distributed approximation algorithms for weighted shortest paths
• Distributed approximation of capacitated dominating sets
• Distributed minimum cut approximation
• Distributed minimum dominating set approximations in restricted families of graphs
• Efficient algorithms for constructing very sparse spanners and emulators
• Fast Distributed Approximation for Max-Cut
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Gadgets, Approximation, and Linear Programming
• Improved Distributed Approximate Matching
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Large cuts with local algorithms on triangle-free graphs
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• Max cut and the smallest eigenvalue
• Maximizing Non-monotone Submodular Functions
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• P-Complete Approximation Problems
• Probability and Computing
• Randomized composable core-sets for distributed submodular maximization
• Reducibility among combinatorial problems
• Semi-supervised learning using greedy Max-Cut
• Some optimal inapproximability results
• Some simplified NP-complete graph problems
• Streaming Lower Bounds for Approximating MAX-CUT
• Weakly bipartite graphs and the max-cut problem
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel

Cited in

(11)

• Fast Distributed Approximation for Max-Cut
• Brief announcement: Low-distortion clustering in bounded growth graphs
• Near-optimal distributed maximum flow
• Local approximation of the maximum cut in regular graphs
• Near-optimal distributed maximum flow (extended abstract)
• scientific article; zbMATH DE number 18532 (Why is no real title available?)
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• Almost-Tight Distributed Minimum Cut Algorithms
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Max-cut under graph constraints
• Adapting local sequential algorithms to the distributed setting

This page was built for publication: Fast Distributed Approximation for Max-Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056049)