Fast Distributed Approximation for Max-Cut

DOI10.1007/978-3-319-72751-6_4zbMath1503.68211arXiv1707.08496MaRDI QIDQ5056049

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

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

68W20: Randomized algorithms

68W15: Distributed algorithms

Related Items

Unnamed Item, Fast Distributed Approximation for Max-Cut, Local approximation of the maximum cut in regular graphs, The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Distributed approximation of capacitated dominating sets
• Weakly bipartite graphs and the max-cut problem
• Some simplified NP-complete graph problems
• Large cuts with local algorithms on triangle-free graphs
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
• $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
• Distributed Minimum Cut Approximation
• Randomized Composable Core-sets for Distributed Submodular Maximization
• Maximizing Non-monotone Submodular Functions
• Improved Distributed Approximate Matching
• Local Computation
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Locality in Distributed Graph Algorithms
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• Distributed Computing: A Locality-Sensitive Approach
• Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
• Max Cut and the Smallest Eigenvalue
• Reducibility among Combinatorial Problems
• Fast Distributed Approximation for Max-Cut
• Distributed approximation algorithms for weighted shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• Distributed Strong Diameter Network Decomposition
• Streaming Lower Bounds for Approximating MAX-CUT
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Probability and Computing