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 ...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.展开更多
In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we al...In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.展开更多
A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization proble...A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.展开更多
基金supported by the National Natural Science Foundation of China(Nos.12271259 and 12371352)the Zhejiang Provincial Natural Science Foundation of China(No.LY23A010011)+1 种基金the Yongjiang Talent Introduction Programme of Ningbo(No.2021B-011-G)the Natural Sciences and Engineering Research Council of Canada(NSERC)(No.06446).
文摘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.
基金supported by the Natural Science Foundation of Shandong Province of China(No.ZR2020MA029).
文摘In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid constraint.In order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm failure.Moreover,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.
基金supported by the Natural Science Foundation of Shandong Province of China(Nos.ZR2020MA029,ZR2021MA100)the National Natural Science Foundation of China(No.12001335).
文摘A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.
