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

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