Hi everyone,

I have the following problem, which, I believe is kind of bayan / old chestnut kind of a problem, but I still need some directions about how I can solve this problem rather efficiently, even if solution is only approximate.

So, let's say we have $$$H \times W$$$ grid. There are $$$n$$$ holes in it of size $$$1 \times 1$$$, placed arbitrary on the grid. We can patch this holes with $$$k \times k$$$ patches. Obviously, it is allowed and even encouraged to apply one patch for several holes at the same time to save up. Let's also say that patches are allowed to intersect. Logically the question here is "How to minimize the amount of patches to cover all the holes?"

After doing a small research, I believe, there is an obvious connection with Set cover problem, which is already pretty studied NP-complete problem on it's own. But I hope, since the structure of the all possible sets is pretty simple and straightforward, there should be some approximations/simple algorithms. So far I googled or came up with the following ideas:

• DP in the case of $$$H$$$ or $$$W$$$ being small (similar to bitmasking DP for the Counting Tiles problem)
• Greedy algo, which adds a new patch covering the most number of holes at the moment
• Some randomization techniques, including but not limited to simulated annealing
• Some simplifications of the problem like decreasing the size of the grid, if all holes are bound to some small region of it or just cover the grid with $$$\dfrac{HW}{k^2}$$$ non-intersecting patches, if amount of holes is big enough

What I'm asking is if you can give me some resources (papers, problems and discussions on Codeforces, other articles on the Internet) on the optimal/fast solutions for this special case of set cover problem

Thank you in advance!