Given a set $P$ of points and a set $U$ of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of $P$ with $U$ is a subset of $U$ that covers $P$ and minimizes the number of squares that share a common intersection, called the minimum ply cover number of $P$ with $U$. Biedl et al. [Comput. Geom., 94:101712, 2020] showed that determining the minimum ply cover number for a set of points by a set of axis-parallel unit squares is NP-hard, and gave a polynomial-time 2-approximation algorithm for instances in which the minimum ply cover number is constant. The question of whether there exists a polynomial-time approximation algorithm remained open when the minimum ply cover number is $\omega(1)$. We settle this open question and present a polynomial-time $(8+\varepsilon)$-approximation algorithm for the general problem, for every fixed $\varepsilon>0$.

翻译：鉴于欧洲加勒比平面的点数和轴-平方单位方形的设定值为美元和美元,以美元计算的最小平面覆盖值是美元的一个子集,包括美元,并尽量减少共同交叉点的平方数,称为最小平面覆盖值为美元。Biedl等人[Comput. Geom.,94:1012,2020]表明,通过一套轴-平面平方形确定一组点的最小平面覆盖值是PP-硬的,对最小平面数字不变的情况给出了多元时间2接近算法。当最小平面覆盖值为美元时,是否存在多元时间近似算法的问题仍然是开放的。我们解决了这个未决问题,并对每个固定的美元/瓦里普西隆0美元的一般问题提出一个聚度时间(8 ⁇ varepsilon)-配价算算法。