关于吹雪机问题的改进近似算法

提出了吹雪机问题的改进近似算法。首先给出了该问题最优解的2个下界，并分析了当待清除区域为单连通区域时问题的难度。对于矩形区域，给出了一个3倍近似度的近似算法。对于任意网格图，算法的近似度为5+ε（任意常数ε＞0）。