近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,...近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,但是当前大部分部署方法仅考虑成本受限约束,而忽略了可充电设备可能具有空间占用的属性.因此,本文考虑了具有空间占用且充电成本受限的可移动传感器调度问题(Charging Cost-Constrained Scheduling,CCS).进一步地,本文以最大化充电效用为目的,提出了一个基于贪心的近似比为(1-1/e)的近似算法.大量仿真实验证明本文算法的优越性,该算法与传统算法对比充电效用提升30%,与粒子群算法对比充电效用提升5%.展开更多
在单无人机辅助的移动边缘计算系统中,为使无人机能服务于大区域中的所有用户设备,可将大区域分成多个子区域,并设定无人机以固定路线在各个子区域间飞行来为用户设备提供计算服务。考虑到用户设备计算资源较匮乏且无人机覆盖区域外的...在单无人机辅助的移动边缘计算系统中,为使无人机能服务于大区域中的所有用户设备,可将大区域分成多个子区域,并设定无人机以固定路线在各个子区域间飞行来为用户设备提供计算服务。考虑到用户设备计算资源较匮乏且无人机覆盖区域外的用户可选择移动至覆盖区域内进行任务卸载以最大化自身效用,可将用户设备的部分卸载问题转化为每个用户设备的效用最大化问题,并利用混合策略博弈和子模博弈来分别确定用户设备的移动概率和卸载数据量,从而得出最优卸载策略,且分别证明了混合策略纳什均衡和纯策略纳什均衡的存在性。仿真结果表明,所提方案与MBO(Binary Offloading Based on Mixed Strategy Game)等经典方案相比可有效提高用户设备的效用,并验证了其收敛性和稳定性。展开更多
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.展开更多
Alzheimer’s disease(AD)is a neurological disorder that predominantly affects the brain.In the coming years,it is expected to spread rapidly,with limited progress in diagnostic techniques.Various machine learning(ML)a...Alzheimer’s disease(AD)is a neurological disorder that predominantly affects the brain.In the coming years,it is expected to spread rapidly,with limited progress in diagnostic techniques.Various machine learning(ML)and artificial intelligence(AI)algorithms have been employed to detect AD using single-modality data.However,recent developments in ML have enabled the application of these methods to multiple data sources and input modalities for AD prediction.In this study,we developed a framework that utilizes multimodal data(tabular data,magnetic resonance imaging(MRI)images,and genetic information)to classify AD.As part of the pre-processing phase,we generated a knowledge graph from the tabular data and MRI images.We employed graph neural networks for knowledge graph creation,and region-based convolutional neural network approach for image-to-knowledge graph generation.Additionally,we integrated various explainable AI(XAI)techniques to interpret and elucidate the prediction outcomes derived from multimodal data.Layer-wise relevance propagation was used to explain the layer-wise outcomes in the MRI images.We also incorporated submodular pick local interpretable model-agnostic explanations to interpret the decision-making process based on the tabular data provided.Genetic expression values play a crucial role in AD analysis.We used a graphical gene tree to identify genes associated with the disease.Moreover,a dashboard was designed to display XAI outcomes,enabling experts and medical professionals to easily comprehend the predic-tion results.展开更多
Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,all...Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,allowing realtime processing of large data sets by examining each piece of data only once.However,most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization.There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.In this paper,we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint.Our 1-pass streaming algorithm for the d-knapsack constraint has a 1/4(d+1)-∈approximation ratio,using O(BlogB/∈)memory,and O(logB/∈)query time per element,where B=MIN(n,b)is the maximum number of elements that the knapsack can store.As a special case of the d-knapsack constraint,we have the 1-pass streaming algorithm with a 1/8-∈approximation ratio to the knapsack constraint.To our knowledge,there is currently no streaming algorithm for this constraint when the objective function is non-monotone,even when d=1.In addition,we propose a multi-pass streaming algorithm with 1/6-∈approximation,which stores O(B)elements.展开更多
文摘近年来,无线能量传输技术(Wireless Power Transmission,WPT)快速发展.这促使在无线可充电传感器网络系统中可部署或调度充电器为可充电设备进行能量补充,以维持系统运行的持续性.基于此,研究者提出多种合作充电模型和相应的调度方法,但是当前大部分部署方法仅考虑成本受限约束,而忽略了可充电设备可能具有空间占用的属性.因此,本文考虑了具有空间占用且充电成本受限的可移动传感器调度问题(Charging Cost-Constrained Scheduling,CCS).进一步地,本文以最大化充电效用为目的,提出了一个基于贪心的近似比为(1-1/e)的近似算法.大量仿真实验证明本文算法的优越性,该算法与传统算法对比充电效用提升30%,与粒子群算法对比充电效用提升5%.
文摘在单无人机辅助的移动边缘计算系统中,为使无人机能服务于大区域中的所有用户设备,可将大区域分成多个子区域,并设定无人机以固定路线在各个子区域间飞行来为用户设备提供计算服务。考虑到用户设备计算资源较匮乏且无人机覆盖区域外的用户可选择移动至覆盖区域内进行任务卸载以最大化自身效用,可将用户设备的部分卸载问题转化为每个用户设备的效用最大化问题,并利用混合策略博弈和子模博弈来分别确定用户设备的移动概率和卸载数据量,从而得出最优卸载策略,且分别证明了混合策略纳什均衡和纯策略纳什均衡的存在性。仿真结果表明,所提方案与MBO(Binary Offloading Based on Mixed Strategy Game)等经典方案相比可有效提高用户设备的效用,并验证了其收敛性和稳定性。
基金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.
文摘Alzheimer’s disease(AD)is a neurological disorder that predominantly affects the brain.In the coming years,it is expected to spread rapidly,with limited progress in diagnostic techniques.Various machine learning(ML)and artificial intelligence(AI)algorithms have been employed to detect AD using single-modality data.However,recent developments in ML have enabled the application of these methods to multiple data sources and input modalities for AD prediction.In this study,we developed a framework that utilizes multimodal data(tabular data,magnetic resonance imaging(MRI)images,and genetic information)to classify AD.As part of the pre-processing phase,we generated a knowledge graph from the tabular data and MRI images.We employed graph neural networks for knowledge graph creation,and region-based convolutional neural network approach for image-to-knowledge graph generation.Additionally,we integrated various explainable AI(XAI)techniques to interpret and elucidate the prediction outcomes derived from multimodal data.Layer-wise relevance propagation was used to explain the layer-wise outcomes in the MRI images.We also incorporated submodular pick local interpretable model-agnostic explanations to interpret the decision-making process based on the tabular data provided.Genetic expression values play a crucial role in AD analysis.We used a graphical gene tree to identify genes associated with the disease.Moreover,a dashboard was designed to display XAI outcomes,enabling experts and medical professionals to easily comprehend the predic-tion results.
基金supported in part by the National Natural Science Foundation of China(Grant Nos.62325210 and 62272441).
文摘Submodular maximization is a significant area of interest in combinatorial optimization.It has various real-world applications.In recent years,streaming algorithms for submodular maximization have gained attention,allowing realtime processing of large data sets by examining each piece of data only once.However,most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization.There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.In this paper,we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint.Our 1-pass streaming algorithm for the d-knapsack constraint has a 1/4(d+1)-∈approximation ratio,using O(BlogB/∈)memory,and O(logB/∈)query time per element,where B=MIN(n,b)is the maximum number of elements that the knapsack can store.As a special case of the d-knapsack constraint,we have the 1-pass streaming algorithm with a 1/8-∈approximation ratio to the knapsack constraint.To our knowledge,there is currently no streaming algorithm for this constraint when the objective function is non-monotone,even when d=1.In addition,we propose a multi-pass streaming algorithm with 1/6-∈approximation,which stores O(B)elements.
