Adapting local sequential algorithms to the distributed setting

DOI10.4230/LIPICS.DISC.2018.35zbMATH Open1497.68566arXiv1711.10155MaRDI QIDQ5090928FDOQ5090928

Authors: Ken-ichi Kawarabayashi, Gregory Schwartzman 

Publication date: 21 July 2022

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

Recommendations

• Fast Distributed Approximation for Max-Cut
• Best of two local models: centralized local and distributed local algorithms
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• On the complexity of local distributed graph problems

zbMATH Keywords

approximation algorithmsdistributed algorithmsderandomizationMax-Cut

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• Clustering with qualitative information
• Aggregating inconsistent information: ranking and clustering
• Correlation clustering
• Gadgets, Approximation, and Linear Programming
• Title not available (Why is that?)
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Some simplified NP-complete graph problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max cut and the smallest eigenvalue
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Locality in Distributed Graph Algorithms
• Correlation clustering in general weighted graphs
• Correlation clustering with a fixed number of clusters
• Correlation clustering, maximizing agreements via semidefinite programming
• An expansion tester for bounded degree graphs
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Distributed approximation of maximum independent set and maximum matching
• Title not available (Why is that?)
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Balanced max 2-sat might not be the hardest
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of local distributed graph problems
• Optimal dynamic distributed MIS
• Analysis 1.
• Large cuts with local algorithms on triangle-free graphs
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Fast Distributed Approximation for Max-Cut

Cited In (3)

• Title not available (Why is that?)
• Local approximation of the maximum cut in regular graphs
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs

This page was built for publication: Adapting local sequential algorithms to the distributed setting

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