Research map / Bandits and online learning / Online convex optimization and games
Fully Online Matching with Stochastic Arrivals and Departures
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 the LP-based SAM algorithm with γ = 7−√17/8 | Fully online matching · Mild conditions: Dv ≥ Varv and Dv ≥ 1 | competitive ratio lower bound: 0.155 | Helped |
| Use the fixed-sojourn-time analysis | SAM · Fixed sojourn times | competitive ratio lower bound: 0.159 | Helped |
| Use geometric sojourn times Geo(pG) | SAM · Geometric sojourn times | competitive ratio lower bound: 0.122 + 0.066pG | Mixed |
| Use binomial sojourn times B(nB, pB) | SAM · Binomial sojourn times with Dv ≥ 1 | competitive ratio lower bound: 0.154 + 0.038/nB | Mixed |
| Use Poisson sojourn times with λP ≥ 1 | SAM · Poisson sojourn times | competitive ratio lower bound: 0.155 | Helped |
| Set γ = 0.5 instead of γ = 0.36 (ablation) | SAM · Synthetic datasets across tested parameter settings | empirical competitive ratio | Helped |
| Set γ = 0.5 instead of γ = 0.36 (ablation) | SAM · Mild-condition theoretical guarantee | competitive ratio lower bound: 0.155; 0.141 | Hurt |
| Use SAM0.5 instead of the baseline algorithms | Matching algorithms on synthetic datasets · Tested parameter settings | empirical competitive ratio | Helped |
| Use SAM rather than BAT as graph density decreases | Matching algorithms on synthetic datasets · Sparse graphs | empirical competitive ratio | Helped |
| Use SAM rather than BAT or GRD as sojourn-time diversity increases | Matching algorithms on synthetic datasets · Geometric sojourn-time distributions | empirical competitive ratio | Helped |
Closest papers by meaning
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.90)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.87)
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.86)
- Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations (ICML 2024 · similarity 0.86)
- Stochastic Matching via Local Sparsification (NeurIPS 2026 · similarity 0.86)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.86)
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.