Fast Distributed Approximation for Max-Cut (Q5056049): Difference between revisions

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