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.展开更多
We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation ...We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.展开更多
当前的基于词向量的多文档摘要方法没有考虑句子中词语的顺序,存在异句同向量问题以及在小规模训练数据上生成的摘要冗余度高的问题。针对这些问题,提出基于PV-DM(Distributed Memory Model of Paragraph Vectors)模型的多文档摘要方法...当前的基于词向量的多文档摘要方法没有考虑句子中词语的顺序,存在异句同向量问题以及在小规模训练数据上生成的摘要冗余度高的问题。针对这些问题,提出基于PV-DM(Distributed Memory Model of Paragraph Vectors)模型的多文档摘要方法。该方法首先构建单调亚模(Submodular)目标函数;然后,通过训练PV-DM模型得到句子向量计算句子间的语义相似度,进而求解单调亚模目标函数;最后,利用优化算法抽取句子生成摘要。在标准数据集Opinosis上的实验结果表明该方法优于当前主流的多文档摘要方法。展开更多
基金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.
基金The first author was supported by the National Natural Science Foundation of China(Nos.12001025 and 12131003)The second author was supported by the Spark Fund of Beijing University of Technology(No.XH-2021-06-03)+2 种基金The third author was supported by the Natural Sciences and Engineering Research Council of Canada(No.283106)the Natural Science Foundation of China(Nos.11771386 and 11728104)The fourth author is supported by the National Natural Science Foundation of China(No.12001335).
文摘We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint.This sum function is non-submodular in general.For an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy algorithm.For a streaming model,we propose a one-pass streaming algorithm.We also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular function.The total curvature is computable in polynomial time and widely utilized in the literature.
基金国家自然科学基金(6117212761401001)+4 种基金高等学校博士学科点专项科研基金(20113401110006)安徽省自然科学基金(1508085MF120)资助Supported by National Natural Science Foundation of China(6117212761401001)Specialized Research Fund for the Doctoral Program of Higher Education of China(20113401110006)and Anhui Provincial Natural Science Foundation(1508085MF120)
文摘当前的基于词向量的多文档摘要方法没有考虑句子中词语的顺序,存在异句同向量问题以及在小规模训练数据上生成的摘要冗余度高的问题。针对这些问题,提出基于PV-DM(Distributed Memory Model of Paragraph Vectors)模型的多文档摘要方法。该方法首先构建单调亚模(Submodular)目标函数;然后,通过训练PV-DM模型得到句子向量计算句子间的语义相似度,进而求解单调亚模目标函数;最后,利用优化算法抽取句子生成摘要。在标准数据集Opinosis上的实验结果表明该方法优于当前主流的多文档摘要方法。
