# Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2021.

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

- [Teal: Learning-Accelerated Optimization of WAN Traffic Engineering](https://mlsanity.com/paper/2210.13763/) (2022)
- [Deep Learning Workload Scheduling in GPU Datacenters: Taxonomy, Challenges and Vision](https://mlsanity.com/paper/2205.11913/) (2022)
- [KAIROS: Building Cost-Efficient Machine Learning Inference Systems with Heterogeneous Cloud Resources](https://mlsanity.com/paper/2210.05889/) (2022)
- [Robust Heuristic Algorithm Design with LLMs](https://mlsanity.com/paper/2510.08755/) (2025)
- [Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach](https://mlsanity.com/paper/2207.11122/) (2022)
- [A Deep Learning Perspective on Network Routing](https://mlsanity.com/paper/2303.00735/) (2023)
- [iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems](https://mlsanity.com/paper/2602.06064/) (2026)
- [Analytically-Driven Resource Management for Cloud-Native Microservices](https://mlsanity.com/paper/2401.02920/) (2024)
- [Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks](https://mlsanity.com/paper/2503.24203/) (2025)
- [Towards VM Rescheduling Optimization Through Deep Reinforcement Learning](https://mlsanity.com/paper/2505.17359/) (2025)
- [Geminet: Learning the Duality-based Iterative Process for Lightweight Traffic Engineering in Changing Topologies](https://mlsanity.com/paper/2506.23640/) (2025)
- [Tesserae: Scalable Placement Policies for Deep Learning Workloads](https://mlsanity.com/paper/2508.04953/) (2025)
- [Quota Marketplace: Dynamic Pricing for Efficient Allocation of ML Training Resources](https://mlsanity.com/paper/2607.09802/) (2026)

## Abstract (arXiv)

Resource allocation problems in many computer systems can be formulated as mathematical optimization problems. However, finding exact solutions to these problems using off-the-shelf solvers is often intractable for large problem sizes with tight SLAs, leading system designers to rely on cheap, heuristic algorithms. We observe, however, that many allocation problems are granular: they consist of a large number of clients and resources, each client requests a small fraction of the total number of resources, and clients can interchangeably use different resources. For these problems, we propose an alternative approach that reuses the original optimization problem formulation and leads to better allocations than domain-specific heuristics. Our technique, Partitioned Optimization Problems (POP), randomly splits the problem into smaller problems (with a subset of the clients and resources in the system) and coalesces the resulting sub-allocations into a global allocation for all clients. We provide theoretical and empirical evidence as to why random partitioning works well. In our experiments, POP achieves allocations within 1.5% of the optimal with orders-of-magnitude improvements in runtime compared to existing systems for cluster scheduling, traffic engineering, and load balancing.