Simultaneous Approximation of Multi-criteria Submodular Function Maximization

作     者：Dong-Lei Du Yu Li Nai-Hua Xiu Da-Chuan Xu 

作者机构：Faculty of Business AdministrationUniversity of New BrunswickFrederictonNB E3B 9Y2Canada Department of MathematicsSchool of ScienceBeijing Jiaotong University3 ShangyuancunHaidian DistrictBeijing 100044China Department of Applied MathematicsBeijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124China 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2014年第2卷第3期

页      面：271-290页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported by the Natural Sciences and Engineering Research Council of Canada(NSERC,No.283103) This work was partially done while the second author was a visiting doctorate student at the Faculty of Business Administration,University of New Brunswick and supported in part by NSERC(No.283103) The research of the third author is supported by the National Basic Research Program of China(No.2010CB732501) The fourth author’s research is supported by National Natural Science Foundation of China(No.11371001) Scientific Research Common Program of Beijing Municipal Commission of Education(No.KM201210005033) 

主　　题：Multi-criteria Submodular function maximization Approximation algorithm Existence 

摘      要：Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical *** this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function *** address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic *** offer complete characterization of the symmetric case and partial results on the asymmetric case.