Sort:
Open Access Issue
Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window
Tsinghua Science and Technology 2025, 30(2): 488-498
Published: 09 December 2024
Abstract PDF (1.9 MB) Collect
Downloads:28

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.

Total 1