# Metadata

- Title: Approximation algorithms for k-submodular maximization subject to a knapsack constraint
- Authors: Hao Xiao, Qian Liu, Yang Zhou, Min Li
- Year: 2023
- Venue: arXiv preprint (`arXiv:2306.14520v3`, June 25, 2023)
- Primary group: k-submodular
- Secondary tags: monotone, non-monotone, knapsack, greedy, enumeration, density-greedy, combinatorial
- Problem: maximizing monotone or non-monotone k-submodular functions under a single knapsack constraint with common item costs
- Main guarantee: gives a `1 / 2 (1 - e^-2)` greedy approximation for the monotone case and the first greedy-type combinatorial guarantee `1 / 3 (1 - e^-3)` for the non-monotone case
- Key techniques: enumerate a constant-size seed, complete it by density-greedy, analyze the first rejected optimum item, and compare transformed optimum sequences against greedy partial solutions
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #knapsack #non-monotone #monotone #greedy #approximation #arXiv
- Inbox source: inbox/2306.14520v3.pdf