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.展开更多
Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization.In this paper,we consider knapsack constraint.In this problem,we give n...Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization.In this paper,we consider knapsack constraint.In this problem,we give n articles and m categories,and the goal is to select a subset of articles that can maximize the function F(S).Function F(S)consists of m monotone submodular functions fj,j=1,2,…,m,and each fj measures the similarity of each article in category j.We present a constant-approximation algorithm for this problem.展开更多
基金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.
基金supported by the National Natural Science Foundation of China(Nos.12131003,12271259,11371001,11771386,and 11728104)the Natural Sciences and Engineering Research Council of Canada(NSERC)(No.06446)+1 种基金the Natural Science Foundation of Jiangsu Province(No.BK20200267)Qinglan Project.
文摘Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization.In this paper,we consider knapsack constraint.In this problem,we give n articles and m categories,and the goal is to select a subset of articles that can maximize the function F(S).Function F(S)consists of m monotone submodular functions fj,j=1,2,…,m,and each fj measures the similarity of each article in category j.We present a constant-approximation algorithm for this problem.
