近期，数学与统计学院李伟东教授在应用数学领域取得多项重要成果。

一、李伟东教授与暨南大学欧锦文教授合作将云边协同计算环境中的一个任务卸载问题刻画成具有惩罚和带宽限制的平行机排序问题，推广了前人研究的一系列经典的离散优化问题。该项成果以“Machine scheduling with restricted rejection: An application to task offloading in cloud–edge collaborative computing”为题在运筹学与管理科学领域国际期刊European Journal of Operational Research上发表。李伟东教授在损失微小近似因子的前提下，将该问题的输入实例转化成具有优美组合结构且相对容易解决的新实例，利用动态规划、数据取整等技术设计了一个多项式时间近似方案（意味着可以得到无限接近于最优值的可行解），比现有结果具有更低的时间复杂度和更强的普适性。当所有任务消耗的带宽几乎相同时，基于大任务组合的结构特征，建立了一个混合整数规划，利用整数变量个数有限的特性进行求解，进而利用带数目约束背包算法的关键性质进行小任务的分配，最终得到了一个高效的多项式时间近似方案，极大地降低了算法的时间复杂度。

二、云边协同计算渐成当前主流的计算范式之一，在空、天、地、海一体化通信网络中发挥着至关重要的作用。如何平衡云边协同计算系统的计算能力和能耗之间关系已成为业内关注的核心问题之一。在“碳达峰、碳中和”大背景下，如何有效降低先进制造中的能量消耗问题引起了相关学者的广泛关注。李伟东教授与欧锦文教授合作针对前人提出的绿色制造中带能量约束的平行机排序问题，通过分析该问题的组合性质，发现了一个通用的引理，借助任务的合理分类与装填技术，设计了一个1.33-近似算法，改进了前人的结果。同时引入单调排序的概念，对任务进行更加精细的分类，有效地控制了能量消耗，进而设计了一个多项式时间近似方案。最后，针对机器数为常数的情形，设计了一个运行时间非常低的全多项式时间近似方案。该项成果以“Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing”为题在运筹学与管理科学领域国际期刊European Journal of Operational Research发表。

三、移动群智感知以大量普通用户的移动设备为基本感知单元，通过物联网和移动互联网进行协作，实现任务分配和数据采集，最终完成城市与社会感知任务，已经成为一种主流的新型感知范式。在当前的移动群智感知任务分配模型中，采集数据所产生的价值一般用具有边际效应递减的次模函数来描述，忽略了用户顺序不同带来的影响。李伟东教授与信息学院张骥先副教授、武浩教授等人合作通过有序次模函数刻画数据价值，将移动群智感知任务分配中的价值最大化问题转化为具有预算约束的有序次模函数最大化模型，结合有序次模和反向拍卖机制的特性，提出了一种有序次模比例共享机制来解决以用户覆盖概率模型为前提的移动群智感知任务分配和支付问题，并证明该机制满足个体理性、可信性和预算可行性的经济学性质。实验结果表明，与现有机制对比，所提出的机制在多项指标上表现出更佳的性能。该项成果以“An ordered submodularity-based budget-feasible mechanism for opportunistic mobile crowdsensing task allocation and pricing”为题，在计算机网络领域国际期刊IEEE Transactions on Mobile Computing发表。

上述研究成果充分展现了数学与管理科学、计算机科学、信息与通信工程、经济学等学科交叉的研究价值，符合应用数学的定位与发展趋势，并得到国家自然科学基金面上项目的资助。

供稿：数学与统计学院

编辑：李哲 责任编辑：王崴