# Metadata

- Title: Corrigendum to "On Maximizing a Monotone k-Submodular Function under a Knapsack Constraint" [Oper. Res. Lett. 50.1 (2022) 28-31]
- Authors: Zhongzheng Tang, Chenhao Wang, Hau Chan
- Year: 2021
- Venue: arXiv preprint (`arXiv:2105.15159v2`, May 31, 2021)
- Primary group: k-submodular
- Secondary tags: corrigendum, monotone, knapsack, greedy, density-greedy, approximation
- Problem: monotone k-submodular maximization under a single knapsack constraint with common item costs
- Main guarantee: corrects the proof of the original ORL letter, keeps the same size-two-seed density-greedy algorithm, and improves the guarantee from `1 / 2 - 1 / (2e)` to `0.4`
- Key techniques: pair enumeration, density-greedy completion, residual function after a guessed seed, first-rejected-optimum-item analysis, and charging through a `1 / 2` unconstrained-greedy bound
- Status: processed-deep, corrigendum, venue-year-to-verify
- Tags: #k-submodular #knapsack #corrigendum #monotone #greedy #approximation #arXiv
- Inbox source: inbox/2105.15159v2.pdf