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 o...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.展开更多
The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper...The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k re- trieval problem in the framework of facility location analysis and prove he submodularity of that objective function which provides a theoretical approximation guarantee of factor 1 -1/ε for the （best-first） greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first ob- tains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.展开更多
基金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)+2 种基金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.
基金This work was supported by the National Natural Science Foundation of China （Grant Nos. 61572135 and 61170085）, 973 project （2010CB328106）, Program for New Century Excellent Talents in China （NCET-10-0388）.
文摘The key issue in top-k retrieval, finding a set of k documents （from a large document collection） that can best answer a user＇s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k re- trieval problem in the framework of facility location analysis and prove he submodularity of that objective function which provides a theoretical approximation guarantee of factor 1 -1/ε for the （best-first） greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first ob- tains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.
