一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法

• 作者: 刘云龙 王建新 许小双 陈建二
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 二分图的受约束最小点覆盖 近似算法 参数计算 PTAS算法
• 年，卷（期）: 2007,（6）
• 所属期刊栏目: 软件工程
• 页码范围: 270-273,282
• 页数: 5页
• 分类号: TP3
• 字数: 8769字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2007.06.075

摘要

二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP.基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε＞1,一定可以找到一个受约束近似点覆盖(ku*,kl*),对应的近似率为max{ku*/ku,kl*/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε).显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	刘云龙	中南大学信息科学与工程学院	23	75	5.0	7.0
4	许小双	中南大学信息科学与工程学院	2	6	2.0	2.0