Large-Scale Generalized Matching
TalkinGermanat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Presents scalable algorithms for generalized matching problems on very large datasets, focusing on parallel and distributed methods. Describes techniques for efficient computation and coordination across machines to solve matching variants (like weighted or constrained matching) at scale, and evaluates their performance on large instances.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:52A Simple Recommender System
- 5:03Solving GBM Problems
- 5:44Overview
- 7:16Mixed Packing-Covering LP
- 11:02Algorithm (E-feasibility)
- 13:00MPCSolver in Practice
- 15:59Dependent Rounding
- 17:07Distributed Rounding
- 20:42Outline
- 22:13Scalability
- 23:28MPCSolver on a GPU
- 23:52Quality (feasibility, ε = 0.05)
- 24:38Summary
related talks
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
07mJoin Algorithms Meet New Constraints: Scalability, Latency and Privacy
51mExploiting Similarity in Federated Learning
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
19mDeterministic Dynamic Matching In Worst-Case Update Time
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
10mQuery, Communication and Discrepancy
44mHow We Store and Analyze a Large Social Graph