• 首页
  • 实验室概况
    • 实验室介绍
    • 实验室管理
    • 学术委员会
    • 实验室组成
    • 规章制度
  • 科学研究
    • 研究方向
    • 研究进展
    • 学术论文
    • 科研项目
  • 研究队伍
    • 序列分析
    • 生物网络分析
    • 医学影像分析
    • 生物数据挖掘
  • 研究生教育
    • 招生指南
    • 导师信息
    • 活动展示
  • 合作交流
    • 学术会议
    • 学术报告
  • 开放课题
    • 通知
    • 申请指南
    • 管理办法
    • 经费细则
    • 申请表格
  • 新闻中心
    • 资讯动态
    • 新闻公告
  • 开源软件
  • 联系我们
当前位置: 首页 >> 科学研究 >> 研究进展 >> 正文

带容量下限k-中值问题的近似算法研究

2022年03月21日 21:12  点击:[]

中南大学计算机学院、生物信息学湖南省重点实验室成员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。


王建新教授团队长期致力于计算机算法与优化、生物信息学、医学影像分析等方面研究。该研究工作得到国家自然科学基金等基金支持。


上一条:IsoCell:一种利用正交投影整合异构体级表达以增强单细胞聚类效果的方法
下一条:基于矩阵填充的多视图学习方法用于药物重定位

【关闭】

版权所有 生物信息学湖南省重点实验室 Copyright ©2020 http://bio.csu.edu.cn/

湖南省长沙市岳麓区麓山南路932号, 410083 电话/传真:(0731)- 88830212 电子邮件:hunan_bio@csu.edu.cn