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.展开更多
Wireless Power Transmission(WPT)has been widely used to replenish energy for various rechargeable devices.The ElectroMagnetic Radiation(EMR)of WPT has attracted great attention of safety concerns.It is possible for th...Wireless Power Transmission(WPT)has been widely used to replenish energy for various rechargeable devices.The ElectroMagnetic Radiation(EMR)of WPT has attracted great attention of safety concerns.It is possible for the malicious attacker to launch the EMR attack by capturing multiple wireless chargers.Little work has studied the EMR attack itself.In this paper,we propose a realistic EMR hazard model,which outputs the diminishing marginal hazard with EMR,with adjustable parameters to the target entities.We formulate three EMR attack models,termed Cumulative EMR Attack(CEA),Overall EMR Attack(OEA)and Unsafety EMR Attack(UEA),and propose the performance guaranteed algorithm of EMR attack for each model.We conduct extensive simulations and field experiments on a testbed.The results show that the proposed algorithms can output the near-optimal solution with much less running time than the optimal algorithms.The results of field experiments in a small testbed show that the utilities of CEAA and OEAA are increased by 70.5%and 12.9%than the comparison algorithms,respectively.Moreover,the number of captured chargers of UEAA is 5.9%less than the comparison algorithms.Our simulations also show the designed algorithms can perform better in a large-scale charging network.展开更多
近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,...近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,但是当前大部分部署方法仅考虑成本受限约束,而忽略了可充电设备可能具有空间占用的属性.因此,本文考虑了具有空间占用且充电成本受限的可移动传感器调度问题(Charging Cost-Constrained Scheduling,CCS).进一步地,本文以最大化充电效用为目的,提出了一个基于贪心的近似比为(1-1/e)的近似算法.大量仿真实验证明本文算法的优越性,该算法与传统算法对比充电效用提升30%,与粒子群算法对比充电效用提升5%.展开更多
当前的基于词向量的多文档摘要方法没有考虑句子中词语的顺序,存在异句同向量问题以及在小规模训练数据上生成的摘要冗余度高的问题。针对这些问题,提出基于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.
基金supported by National Natural Science Foundation of China(No.62372249,No.62072254)Jiangsu Graduate Scientific Research Innovation Program(No.KYCX210796).
文摘Wireless Power Transmission(WPT)has been widely used to replenish energy for various rechargeable devices.The ElectroMagnetic Radiation(EMR)of WPT has attracted great attention of safety concerns.It is possible for the malicious attacker to launch the EMR attack by capturing multiple wireless chargers.Little work has studied the EMR attack itself.In this paper,we propose a realistic EMR hazard model,which outputs the diminishing marginal hazard with EMR,with adjustable parameters to the target entities.We formulate three EMR attack models,termed Cumulative EMR Attack(CEA),Overall EMR Attack(OEA)and Unsafety EMR Attack(UEA),and propose the performance guaranteed algorithm of EMR attack for each model.We conduct extensive simulations and field experiments on a testbed.The results show that the proposed algorithms can output the near-optimal solution with much less running time than the optimal algorithms.The results of field experiments in a small testbed show that the utilities of CEAA and OEAA are increased by 70.5%and 12.9%than the comparison algorithms,respectively.Moreover,the number of captured chargers of UEAA is 5.9%less than the comparison algorithms.Our simulations also show the designed algorithms can perform better in a large-scale charging network.
文摘近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,但是当前大部分部署方法仅考虑成本受限约束,而忽略了可充电设备可能具有空间占用的属性.因此,本文考虑了具有空间占用且充电成本受限的可移动传感器调度问题(Charging Cost-Constrained Scheduling,CCS).进一步地,本文以最大化充电效用为目的,提出了一个基于贪心的近似比为(1-1/e)的近似算法.大量仿真实验证明本文算法的优越性,该算法与传统算法对比充电效用提升30%,与粒子群算法对比充电效用提升5%.
基金国家自然科学基金(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上的实验结果表明该方法优于当前主流的多文档摘要方法。
