Timezone: »
Maximum weight matching is one of the most fundamental combinatorial optimization problems with a wide range of applications in data mining and bioinformatics. Developing distributed weighted matching algorithms has been challenging due to the sequential nature of efficient algorithms for this problem. In this paper, we develop a simple distributed algorithm for the problem on general graphs with approximation guarantee of 2 + eps that (nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that it can be easily implemented in only two rounds of computation in modern parallel computation frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on various graphs (some with half a trillion edges) by achieving objective values always close to what is achievable in the centralized setting.
Author Information
Sepehr Assadi (Princeton University)
Mohammad Hossein Bateni (Google Research)
Vahab Mirrokni (Google Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Distributed Weighted Matching via Randomized Composable Coresets »
Thu. Jun 13th 01:30 -- 04:00 AM Room Pacific Ballroom #161
More from the Same Authors
-
2023 : Preference Elicitation for Music Recommendations »
Ofer Meshi · Jon Feldman · Li Yang · Ben Scheetz · Yanli Cai · Mohammad Hossein Bateni · Corbyn Salisbury · Vikram Aggarwal · Craig Boutilier -
2023 : Tackling Provably Hard Representative Selection viaGraph Neural Networks »
Mehran Kazemi · Anton Tsitsulin · Hossein Esfandiari · Mohammad Hossein Bateni · Deepak Ramachandran · Bryan Perozzi · Vahab Mirrokni -
2023 : Sequential Attention for Feature Selection »
Taisuke Yasuda · Mohammad Hossein Bateni · Lin Chen · Matthew Fahrbach · Thomas Fu · Vahab Mirrokni -
2023 : Tensor Proxies for Efficient Feature Cross Search »
Taisuke Yasuda · Mohammad Hossein Bateni · Lin Chen · Matthew Fahrbach · Thomas Fu -
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Oral: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Poster: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 Spotlight: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 : Closing Remarks »
Vahab Mirrokni -
2022 : Private Algorithms Q/A »
Peilin Zhong · Alessandro Epasto · Vahab Mirrokni -
2022 : Graph Mining Q/A »
Vahab Mirrokni -
2022 : New Challenges in Graph Mining: Scalability, Stability, and Privacy Applications »
Vahab Mirrokni -
2022 Expo Talk Panel: Challenges Of Applying Graph Neural Networks »
Bryan Perozzi · Vahab Mirrokni -
2022 : Graph Mining at Google »
Vahab Mirrokni -
2021 Poster: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Spotlight: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Poster: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Spotlight: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Poster: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2021 Spotlight: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2020 Poster: Robust Pricing in Dynamic Mechanism Design »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni -
2020 Poster: Dual Mirror Descent for Online Allocation Problems »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2020 Poster: Bandits with Adversarial Scaling »
Thodoris Lykouris · Vahab Mirrokni · Renato Leme -
2019 Poster: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2019 Poster: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Poster: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2018 Oral: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2017 Poster: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong -
2017 Talk: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong