pipette
ENEnglish

A Combinatorial -Approximation for -Submodular Maximization under Multiple Knapsacks

Siyuan Chen, Suixiang Gao, Zheyu Jiang, and Wenguo Yang

Preprint

En palabras de los autores

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 value queries, where is the number of elements, depends only on and , and . The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 23 pages