Improved method breaks one third barrier in label assignment optimization
Breaking the 1/3 Barrier for $\boldsymbol{k}$-Submodular Maximization under Matroid and Knapsack Constraints: A Proportional Top-2 Randomized Framework
Data Structures and Algorithms
Summary
The paper studies a problem where items must be selected and assigned one of several labels to maximize a certain value, under some rules like budget or independence. Earlier methods could only guarantee a solution that was about one third as good as the best possible. The authors show a new way to pick items and assign labels that improves this guarantee to about 41%, meaning better solutions can be found more reliably. Their approach randomly chooses from the two best label options for each item, balancing simplicity and power.
What this means in practice
- •For data engineers: Optimize complex resource assignments under budget or organizational rules more effectively than before with improved approximation guarantees.
- •For operations research analysts: Improve solution quality for combinatorial optimization problems involving multi-label decisions subject to classic constraints like matroids or knapsack limits.
Authors
Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Chenhao Wang, Wenguo Yang
Abstract
$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels, rather than being merely selected or not selected. We study the problem of maximizing a nonnegative non-monotone $k$-submodular function, where $k\ge 2$, under classical support constraints, including a single matroid constraint and a single knapsack constraint. Previously, the best known approximation guarantees for non-monotone constrained $k$-submodular maximization had long remained at $1/3$ or $1/3-\varepsilon$, even in basic settings such as cardinality, matroid, and knapsack constraints. We show that this $1/3$ barrier is not inherent: for both the matroid and knapsack settings considered here, we give randomized polynomial-time algorithms achieving an approximation ratio of $\sqrt{2}-1\approx 0.4142$. The algorithms use a simple randomized greedy rule: once an element is selected, its label is chosen only from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these two gains. The value-oracle query complexity is $O(n^2k)$ in the matroid setting and $O(n^3k^2)$ in the knapsack setting. These results give the first approximation guarantees exceeding $1/3$ for non-monotone $k$-submodular maximization under matroid and knapsack constraints.