Submodular function maximization problem has been extensively studied recently. A natural variant of submodular function is k-submodular function, which has many applications in real life, such as influence maximization and sensor placement problem. The domain of a k-submodular function has k disjoint subsets, and hence includes submodular function as a special case when k=1. This work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding window. Based on the smooth histogram technique, we design a deterministic approximation algorithm. Furthermore, we propose a randomized algorithm to improve the approximation ratio.
Publications
- Article type
- Year
- Co-author
Year

Tsinghua Science and Technology 2025, 30(2): 488-498
Published: 09 December 2024
Downloads:28
Total 1