%0 Journal Article
%T 关于吹雪机问题的改进近似算法
%A 李建
%A 王海涛
%A 朱洪
%J 吉林大学学报(工学版)
%P 151-154
%D 2007
%X 提出了吹雪机问题的改进近似算法。首先给出了该问题最优解的2个下界，并分析了当待清除区域为单连通区域时问题的难度。对于矩形区域，给出了一个3倍近似度的近似算法。对于任意网格图，算法的近似度为5+ε（任意常数ε＞0）。
%K 计算机应用
%K 吹雪机问题
%K NP-hard
%K 近似算法
%K 计算机应用
%K 吹雪机问题
%K NP-hard
%K 近似算法
%U http://xuebao.jlu.edu.cn/gxb/CN/Y2007/V37/I01/151