近日，浙江师范大学计算机科学与技术学院青年教师梁威博士以浙江师范大学为第一署名单位，以第一作者身份连续在数学优化领域顶级期刊Mathematical Programming及中国计算机学会（CCF）推荐的计算机网络领域A类期刊IEEE/ACM Transactions on Networking上发表了两篇高水平学术论文。
论文一：Approximation Algorithm for Unrooted Prize-Collecting Forest with Multiple Components and Its Application on Prize-Collecting Sweep Coverage（Mathematical Programming）。Mathematical Programming是数学优化领域顶级期刊，属于中国数学学会推荐T1类期刊。浙师大为论文第一单位和通讯单位，梁威博士为论文第一作者，纽约州立大学布法罗分校唐少杰教授为第二作者，数学科学学院张昭教授为通讯作者。
本文针对带K个连通分支的无根奖励收集森林问题（URPCF-K）提出了一种多项式时间的2－近似算法。给定图G和整数K，URPCF-K问题旨在找到一个恰好包含K个连通分支的森林，同时最小化森林成本与未覆盖顶点惩罚值之和。该问题是理论计算机科学领域经典问题奖励收集斯坦纳树问题（PCST）的一个推广问题。与存在2－近似算法的有根版本不同，通过猜测根节点来解决无根版本会导致非常数K情况下的指数级时间复杂度，为解决这一难题，本文创造性地设计了“增强对偶规划”和“双层嵌套动态规划”等方法，成功得到了多项式时间的2－近似算法，并将该算法应用于奖励收集巡检覆盖问题，将其近似比从8提升至5。
论文二：A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensor（IEEE/ACM Transactions on Networking，TON）。TON是计算机网络领域的顶级期刊，属于CCF-A类期刊。浙师大为论文第一单位和通讯单位，梁威博士为论文第一作者，纽约州立大学布法罗分校唐少杰教授为第二作者，数学科学学院张昭教授为通讯作者。
本文针对预算限制下的巡检覆盖问题（BSC），给出了第一个常数近似算法，解决了BSC是否存在常数近似的公开问题。给定N个移动传感器，BSC的目标是用这N个传感器周期性地访问尽可能多的目标点。该问题是计算机网络设计和机器人路径规划领域的一个重要问题，但在本文之前，还不存在一般情况下的常数近似算法。通过提出多人定向问题（MOP）这一子问题并创新性地用多条路对目标点分组，本文为BSC设计了第一个常数近似算法。
梁威，浙江师范大学计算机学院讲师，博士毕业于浙江师范大学，师从张昭教授。主要研究兴趣为近似算法、组合优化、网络上的覆盖问题等。已在Mathematical Programming、IEEE/ACM Transactions on Networking、INFORMS Journal on Computing、Optimization Letters等学术期刊发表多篇论文。
编辑：盛灿灿
