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