Research map / Learning theory and algorithms / Submodular and game algorithms
Randomized Mechanisms for Selling Reserved Instances in Cloud
Jia Zhang, Weidong Ma, Tao Qin, Xiaoming Sun, Tie-Yan Liu
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 randomized threshold-price filtration before greedy scheduling | Random-Pricing · Online reserved-instance allocation, k=T=2 | social welfare competitive ratio: \frac{1}{42} | Improved |
| Use randomized threshold-price filtration before greedy scheduling | Random-Pricing · Online reserved-instance allocation, k=T=2 | revenue competitive ratio: \frac{1}{42} | Improved |
| Bound each request's resource use by αC and use greedy acceptance with price ρ_min c_j t_j | Greedy · Online reserved-instance allocation, k=T=2, c_j/C≤α≤0.5 | social welfare competitive ratio: \frac{1-\alpha}{11-\alpha} | Improved |
| Bound each request's resource use by αC and use greedy acceptance with price ρ_min c_j t_j | Greedy · Online reserved-instance allocation, k=T=2, c_j/C≤α≤0.5 | revenue competitive ratio: \frac{1-\alpha}{11-\alpha} | Improved |
| Randomly select value-density and request-length bins and filter using the resulting threshold price | Binary-Filter · Online reserved-instance allocation, general k and T | social welfare competitive ratio: \frac{1}{42\ceil{\log k}\ceil{\log T}} | Improved |
| Randomly select value-density and request-length bins and filter using the resulting threshold price | Binary-Filter · Online reserved-instance allocation, general k and T | revenue competitive ratio: \frac{1}{42\ceil{\log k}\ceil{\log T}} | Improved |
| Remove the random resource-size choice under the bounded-request-size constraint | Binary-Filter · Online reserved-instance allocation, general k and T, c_j/C≤α≤1/2 | social welfare competitive ratio: \frac{1-\alpha}{(11-\alpha)\ceil{\log k}\ceil{\log T}} | Improved |
| Remove the random resource-size choice under the bounded-request-size constraint | Binary-Filter · Online reserved-instance allocation, general k and T, c_j/C≤α≤1/2 | revenue competitive ratio: \frac{1-\alpha}{(11-\alpha)\ceil{\log k}\ceil{\log T}} | Improved |
| Omit the threshold-price filtration | Random-Pricing · Online reserved-instance allocation | social welfare | Hurt |
Closest papers by meaning
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.83)
- Test-Time Compute Games (NeurIPS 2026 · similarity 0.83)
- Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation (ICML 2024 · similarity 0.82)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.82)
- Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · similarity 0.81)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.81)
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.
