Adapting local sequential algorithms to the distributed setting

DOI10.4230/LIPICS.DISC.2018.35MaRDI QIDQ5090928zbMATH OpenFDO

Authors Ken-ichi Kawarabayashi, Gregory Schwartzman

Publication date 21 July 2022

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

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)

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

Cites work

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

Cited in

(3)

• Local approximation of the maximum cut in regular graphs
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• scientific article; zbMATH DE number 2156277 (Why is no real title available?)

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)