Research map / Learning theory and algorithms / Submodular and game algorithms
Distributed Weighted Matching via Randomized Composable Coresets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized greedy coresets with greedy post-processing instead of sequential greedy on the full graph | Weighted matching · Friendster, Orkut, LiveJournal, and DBLP | weight relative to sequential greedy: 99.83%; 98.90%; 99.86%; 99.55% | Mixed |
| Use randomized greedy coresets to parallelize greedy matching | Weighted matching · Friendster, Orkut, LiveJournal, and DBLP | speed-up over sequential greedy: 130x; 17x; 6x; 3x | Helped |
| Use randomized greedy coresets rather than the Assadi-Khanna method extended with Crouch-Stubbs | Weighted matching · Friendster, Orkut, LiveJournal, and DBLP | weight relative to sequential greedy: 94.43% vs 99.83%; 92.41% vs 98.90%; 96.52% vs 99.86%; 92.42% vs 99.55% | Helped |
| Increase the coreset multiplicity parameter (ablation) | Greedy coreset · Matching quality; two values of k | relative weight and cardinality | Helped |
| Use multiple coresets and combine their edges instead of returning the best greedy matching from one sampled subgraph (ablation) | Greedy coreset · Matching quality as the number of pieces increases | relative solution quality | Helped |
| Reduce Crouch-Stubbs \varepsilon from 1.0 to 0.01 (ablation) | Assadi-Khanna weighted-matching extension · LiveJournal | weight relative to sequential greedy: 87.58% -> 96.52% | Helped |
| Remove the Crouch-Stubbs reduction (ablation) | Assadi-Khanna weighted-matching extension · LiveJournal | weight relative to sequential greedy: 96.52% -> 22.16% | Hurt |
| Use greedy rather than an offline near-optimal matching algorithm for final post-processing (ablation) | Greedy coreset · General graphs | approximation ratio: 2+\varepsilon -> 3+\varepsilon | Hurt |
Closest papers by meaning
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.85)
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.84)
- An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem (AAAI 2025 · similarity 0.84)
- Proportionally Fair Matching via Randomized Rounding (AAAI 2025 · similarity 0.84)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.83)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.