中南大学计算机学院、生物信息学湖南省重点实验室成员2021级博士研究生吴小良在理论计算机科学领域取得重要研究成果。该研究成果以“An approximation algorithm for lower-bounded k-median with constant factor”为题，在期刊《SCIENCE CHINA Information Sciences》（CCF-B类）以论文形式在线发表。
给定度量空间中的一组设施点集合F和客户点集合C，带容量下限k-中值问题的目标是寻找F中一个大小为k的子集S和一个分配函数f : C -> S，使得C中的所有客户点c到其分配的设施点f(c)距离之和最小，并且要求f分配给每个设施点的客户点数量至少为B。带容量下限k-中值问题是聚类领域中一个经典的NP-难解问题。本研究为带容量下限k-中值问题提出了一个多项式时间内的常数近似算法。算法通过多次规约成功地将该问题转化为带容量上限k-中值问题，并基于已有的带容量上限k-中值问题的近似算法，最终为该问题给出了一个多项式时间内的近似算法，并成功证明该近似比为516。
王建新教授团队长期致力于计算机算法与优化、生物信息学、医学影像分析等方面研究。该研究工作得到国家自然科学基金等基金支持。