Research map / Learning theory and algorithms / Submodular and game algorithms
Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 the MP-based algorithm rather than Greedy | Online submodular matching on MovieLens with fractional arrival rates · MovieLens | ratio | Improved |
| Use the MP-based algorithm rather than the CR-based algorithm | Online submodular matching on MovieLens with fractional arrival rates · MovieLens | ratio | Improved |
| Use integral arrival rates for the CR-based algorithm | CR-based · MovieLens, integral arrival rates | ratio | Improved |
| Use the CR-based algorithm for the budget-additive objective with fractional arrival rates | CR-based · Synthetic budget-additive experiments | performance | No clear effect |
| Use the MP-based algorithm rather than the other algorithms | Movie recommendation · MovieLens, b=15, η=5 | genre coverage: greater than 50 % and all the way up to 90% | Improved |
| Use the MP-based algorithm rather than the other algorithms | Movie recommendation · MovieLens, b=15, η=5 | genre coverage: at most 20 - 30% | Improved |
| Increase B for Greedy | Greedy · MovieLens | ratio | Hurt |
| Use the MP-based online phase rather than the CR-based online phase | OSBM · OSBM, arbitrary arrival rates; |U|=o(\sqrt{T}), T \rightarrow \infty | competitive ratio: (1-1/e)^2 | Improved |
Closest papers by meaning
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.92)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.88)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.87)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.86)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.85)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.85)
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.
