Fast Distributed Approximation for Max-Cut
From MaRDI portal
Publication:5056049
DOI10.1007/978-3-319-72751-6_4zbMath1503.68211arXiv1707.08496OpenAlexW2963634340MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items
Fast Distributed Approximation for Max-Cut, The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs, Unnamed Item, Local approximation of the maximum cut in regular graphs
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
