# Overcommitment in Cloud Services -- Bin packing with Chance Constraints

arXiv: https://arxiv.org/abs/1705.09335 · HTML: https://mlsanity.com/paper/1705.09335/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2017.

## Built on by (most cited first, 5 of 5)

- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach](https://mlsanity.com/paper/2207.11122/) (2022)
- [Learning Cooperative Oversubscription for Cloud by Chance-Constrained Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.11759/) (2022)
- [COIN: Chance-Constrained Imitation Learning for Uncertainty-aware Adaptive Resource Oversubscription Policy](https://mlsanity.com/paper/2401.07051/) (2024)
- [Designing Datacenter Power Delivery Hierarchies for the AI Era](https://mlsanity.com/paper/2605.16255/) (2026)

## Abstract (arXiv)

This paper considers a traditional problem of resource allocation, scheduling jobs on machines. One such recent application is cloud computing, where jobs arrive in an online fashion with capacity requirements and need to be immediately scheduled on physical machines in data centers. It is often observed that the requested capacities are not fully utilized, hence offering an opportunity to employ an overcommitment policy, i.e., selling resources beyond capacity. Setting the right overcommitment level can induce a significant cost reduction for the cloud provider, while only inducing a very low risk of violating capacity constraints. We introduce and study a model that quantifies the value of overcommitment by modeling the problem as a bin packing with chance constraints. We then propose an alternative formulation that transforms each chance constraint into a submodular function. We show that our model captures the risk pooling effect and can guide scheduling and overcommitment decisions. We also develop a family of online algorithms that are intuitive, easy to implement and provide a constant factor guarantee from optimal. Finally, we calibrate our model using realistic workload data, and test our approach in a practical setting. Our analysis and experiments illustrate the benefit of overcommitment in cloud services, and suggest a cost reduction of 1.5% to 17% depending on the provider's risk tolerance.