Research map / Bandits and online learning / Online convex optimization and games
Simple and Optimal Greedy Online Contention Resolution Schemes
Vasilis Livanos
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 |
|---|---|---|---|
| Replace the previous single-item greedy OCRS with the proposed randomized greedy OCRS | Single-item greedy OCRS · Single-item | selectability: \nicefrac{1}{4} -> \nicefrac{1}{e} | Improved |
| Apply the single-item greedy OCRS independently across partition classes | Partition matroids · Partition matroids | selectability: \nicefrac{1}{4} -> \nicefrac{1}{e} | Improved |
| Use the proposed greedy scheme for transversal matroids | Transversal matroid greedy OCRS · Transversal matroids | selectability: \nicefrac{1}{4} -> \nicefrac{1}{e} | Improved |
| Require every element to have at least three neighbors | Transversal matroid greedy OCRS · Transversal matroids with |N(u)| >= 3 for every u | selectability: \nicefrac{1}{e} -> 1 - \nicefrac{1}{e} | Improved |
| Use a greedy rather than a non-greedy scheme | Single-item OCRS · Single-item | selectability: \nicefrac{1}{2} -> \nicefrac{1}{e} | Hurt |
| Allow selectability greater than \nicefrac{1}{e} for a greedy OCRS | Single-item greedy OCRS · Single-item | selectability: \nicefrac{1}{e} + \eps | No clear effect |
Closest papers by meaning
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.87)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.86)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.86)
- Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees (AAAI 2024 · similarity 0.86)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.86)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · 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.
