# Solving Billion-Scale Knapsack Problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2020.

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

- [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025)
- [A framework for massive scale personalized promotion](https://mlsanity.com/paper/2108.12100/) (2021)
- [A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs](https://mlsanity.com/paper/2201.00402/) (2021)

## Abstract (arXiv)

Knapsack problems (KPs) are common in industry, but solving KPs is known to be NP-hard and has been tractable only at a relatively small scale. This paper examines KPs in a slightly generalized form and shows that they can be solved nearly optimally at scale via distributed algorithms. The proposed approach can be implemented fairly easily with off-the-shelf distributed computing frameworks (e.g. MPI, Hadoop, Spark). As an example, our implementation leads to one of the most efficient KP solvers known to date -- capable to solve KPs at an unprecedented scale (e.g., KPs with 1 billion decision variables and 1 billion constraints can be solved within 1 hour). The system has been deployed to production and called on a daily basis, yielding significant business impacts at Ant Financial.