@article{Wang2025, 
author = {Wenqi Wang and Yuefang Sun and Zhiren Sun and Donglei Du and Xiaoyan Zhang},
title = {Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window},
year = {2025},
journal = {Tsinghua Science and Technology},
volume = {30},
number = {2},
pages = {488-498},
keywords = {approximation algorithm, sliding window, streaming algorithm, k-submodular function, d-knapsack constraints},
url = {https://www.sciopen.com/article/10.26599/TST.2023.9010121},
doi = {10.26599/TST.2023.9010121},
abstract = {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.}
}