摘要
本文针对一类强NP-Complete问题近似算法的设计问题,提出一种通用的设计策略DPBD,它通过一局部近似算法而获得一全局近似算法,并保证精度在一定范围内.最后,本文将DPBD应用于一著名的NP难度问题:平面Covering问题,对方法的有效性给予了证实.
The paper devises a general designing method DPBD for the approximation algorithm of a kind of NP-complete problems. DPBD can get a global approximation algorithm from a local one and keep the precision to a definite range. At last, DPBD has been used to solve planar covering problem, thus the effectiveness of the method is Verified.
出处
《电子学报》
EI
CAS
CSCD
北大核心
1992年第11期63-68,共6页
Acta Electronica Sinica
关键词
计算机
算法
DPBD方法
NP-Complete problem, Approximation algorithm, DPBD method, Planar covering problem, Global approximaton. algoritbhm, Local approximation algorithm
