Distributed balanced partitioning via linear embedding

DOI10.3390/a12080162zbMath1461.68141arXiv1512.02727OpenAlexW2966909581MaRDI QIDQ2005567

Kevin Aydin, MohammadHossein Bateni, Vahab S. Mirrokni

Publication date: 8 October 2020

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

mapsimbalancepartitioningsocial networksMapReducelocal improvementcut minimizationembedding to line

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (4)

Improved parameterized approximation for balanced \(k\)-median ⋮ Design and analysis of bipartite experiments under a linear exposure-response model ⋮ Approximation algorithms for the load-balanced capacitated vehicle routing problem ⋮ On parameterized approximation algorithms for balanced clustering

Uses Software

• MapReduce
• Pregel
• PEGASUS
• Blogel

Cites Work

• Unnamed Item
• An improved approximation ratio for the minimum linear arrangement problem
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• Balanced graph partitioning
• Towards optimal locality in mesh-indexings
• Global optimization with non-convex constraints. Sequential and parallel algorithms
• Optimal linear arrangement of a rectangular grid
• A Polylogarithmic Approximation of the Minimum Bisection
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• New Approximation Techniques for Some Linear Ordering Problems
• Exact Combinatorial Branch-and-Bound for Graph Bisection
• Streaming Balanced Graph Partitioning Algorithms for Random Graphs

This page was built for publication: Distributed balanced partitioning via linear embedding