Simultaneous Approximation of Multi-criteria Submodular Function Maximization  

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

机构地区：[1]Faculty of Business Administration,University of New Brunswick,Fredericton,NB E3B 9Y2,Canada [2]Department of Mathematics,School of Science,Beijing Jiaotong University,3 Shangyuancun,Haidian District,Beijing 100044,China [3]Department of Applied Mathematics,Beijing University of Technology,100 Pingleyuan,Chaoyang District,Beijing 100124,China

出　　处：《Journal of the Operations Research Society of China》2014年第3期271-290,共20页中国运筹学会会刊（英文）

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

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

关 键 词：MULTI-CRITERIA Submodular function maximization Approximation algorithm EXISTENCE 

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