Two-Stage Submodular Maximization Under Knapsack Problem  

作　　者：Zhicheng Liu Jing Jin Donglei Du Xiaoyan Zhang 

机构地区：[1]Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China [2]College of Taizhou,Nanjing Normal University,Taizhou 225300,China [3]Faculty of Management,University of New Brunswick,Fredericton,E3B 5A3,Canada [4]School of Mathematical Science,Institute of Mathematics,and Ministry of Education Key Laboratory of NSLSCS,Nanjing Normal University,Nanjing 210023,China

出　　处：《Tsinghua Science and Technology》2024年第6期1703-1708,共6页清华大学学报自然科学版（英文版）

基　　金：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);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.

关 键 词：submodular function knapsack constraint MATROID 

分 类 号：O174[理学—数学]