scientific article; zbMATH DE number 7561287

DOI10.4230/LIPIcs.DISC.2018.35zbMath1497.68566arXiv1711.10155MaRDI QIDQ5090928

Gregory Schwartzman, Ken-ichi Kawarabayashi

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmsdistributed algorithmsderandomizationMax-Cut

Mathematics Subject Classification ID

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

Related Items (2)

Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Local approximation of the maximum cut in regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Some simplified NP-complete graph problems
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Large cuts with local algorithms on triangle-free graphs
• Correlation clustering in general weighted graphs
• Clustering with qualitative information
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Locality in Distributed Graph Algorithms
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Max Cut and the Smallest Eigenvalue
• On the complexity of local distributed graph problems
• Reducibility among Combinatorial Problems
• Fast Distributed Approximation for Max-Cut
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Optimal Dynamic Distributed MIS
• Distributed Approximation of Maximum Independent Set and Maximum Matching
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• An Expansion Tester for Bounded Degree Graphs
• Aggregating inconsistent information
• Analysis 1.

This page was built for publication: