Improved approximation for maximizing complex functions with multiple constraints
A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks
Data Structures and Algorithms
Summary
This paper deals with finding good solutions for a complex type of problem where you want to maximize certain values subject to several budget limits (knapsacks). The authors provide an improved random algorithm that picks whole items smartly, achieving about half of the best possible value under multiple constraints. They build on previous methods and handle technical difficulties by breaking the problem into parts and making educated guesses. Their approach works well especially for two options and remains effective when the problem scales up.
What this means in practice
- •For resource allocation teams: Design allocation algorithms that select sets of options respecting multiple budget limits with reliable near-optimal value guarantees.
- •For cloud infrastructure operators: Improve resource scheduling strategies under multiple capacity constraints to better maximize utility of resource assignments.
A theory result. No direct application yet.
Authors
Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
Abstract
We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).