计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2007年
6期
270-273,282
,共5页
许小双%王建新%刘云龙%陈建二
許小雙%王建新%劉雲龍%陳建二
허소쌍%왕건신%류운룡%진건이
二分图的受约束最小点覆盖%近似算法%参数计算%PTAS算法
二分圖的受約束最小點覆蓋%近似算法%參數計算%PTAS算法
이분도적수약속최소점복개%근사산법%삼수계산%PTAS산법
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP.基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε＞1,一定可以找到一个受约束近似点覆盖(ku*,kl*),对应的近似率为max{ku*/ku,kl*/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε).显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法).
二分圖受約束最小點覆蓋問題作為一箇NP-完全問題,無法在多項式時間內得到最優解,除非P=NP.基于此,本文提齣瞭一種基于鏈暗示技術的二分圖受約束最小點覆蓋問題的近似算法,具體為:噹二分圖受約束最小點覆蓋問題實例中存在滿足約束條件的最小點覆蓋(ku,kl)時,對任意給定的近似率δ=1+ε＞1,一定可以找到一箇受約束近似點覆蓋(ku*,kl*),對應的近似率為max{ku*/ku,kl*/kl}≤1+ε,整箇近似算法的運行時間複雜度為O(22/ε).顯然,它是二分圖受約束最小點覆蓋問題的一箇多項式時間近似方案(polynomial time approximation scheme,PTAS算法).
이분도수약속최소점복개문제작위일개NP-완전문제,무법재다항식시간내득도최우해,제비P=NP.기우차,본문제출료일충기우련암시기술적이분도수약속최소점복개문제적근사산법,구체위:당이분도수약속최소점복개문제실례중존재만족약속조건적최소점복개(ku,kl)시,대임의급정적근사솔δ=1+ε＞1,일정가이조도일개수약속근사점복개(ku*,kl*),대응적근사솔위max{ku*/ku,kl*/kl}≤1+ε,정개근사산법적운행시간복잡도위O(22/ε).현연,타시이분도수약속최소점복개문제적일개다항식시간근사방안(polynomial time approximation scheme,PTAS산법).
