# Metadata

- Title: A 1/2-Approximation for Budgeted k-Submodular Maximization
- Authors: Chenhao Wang
- Year: 2025
- Venue: arXiv preprint (`arXiv:2507.12875v1`, July 17, 2025)
- Primary group: k-submodular
- Secondary tags: monotone, non-monotone, knapsack, budgeted, greedy, multilinear-extension, approximation
- Problem: budgeted k-submodular maximization under a single knapsack constraint, for both monotone and non-monotone objectives
- Main guarantee: proves that `1-Guess Greedy` achieves the long-sought `1/2` approximation for monotone k-submodular knapsack maximization and `1/3` for the non-monotone case, with `O(n^3 k^2)` value-oracle queries and a thresholded `~O(n^2 k^2)` variant losing only an `epsilon` factor
- Key techniques: continuous transformation from an optimal solution to the greedy partial solution, analysis through the `k`-multilinear extension, reduction to cost-ratio lemmas, and singleton guessing to absorb the rejected high-cost part of the optimum
- Status: processed-deep
- Tags: #k-submodular #knapsack #budgeted #greedy #multilinear-extension #approximation #arXiv
- Inbox source: inbox/2507.12875v1.pdf