# Simple Deterministic Approximation for Submodular Multiple Knapsack Problem

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

## Key facts

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

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

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [SlimCaching: Edge Caching of Mixture-of-Experts for Distributed Inference](https://mlsanity.com/paper/2507.06567/) (2025)

## Abstract (arXiv)

Submodular maximization has been a central topic in theoretical computer science and combinatorial optimization over the last decades. Plenty of well-performed approximation algorithms have been designed for the problem over a variety of constraints. In this paper, we consider the submodular multiple knapsack problem (SMKP). In SMKP, the profits of each subset of elements are specified by a monotone submodular function. The goal is to find a feasible packing of elements over multiple bins (knapsacks) to maximize the profit. Recently, Fairstein et al.~[ESA20] proposed a nearly optimal (1-e-1-ε)-approximation algorithm for SMKP. Their algorithm is obtained by combining configuration LP, a grouping technique for bin packing, and the continuous greedy algorithm for submodular maximization. As a result, the algorithm is somewhat sophisticated and inherently randomized. In this paper, we present an arguably simple deterministic combinatorial algorithm for SMKP, which achieves a (1-e-1-ε)-approximation ratio. Our algorithm is based on very different ideas compared with Fairstein et al.~[ESA20].