3
$\begingroup$

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$.

Consider the following greedy algorithm. At each iteration, it chooses a rectangle of area $\le k$ which covers as many uncovered elements as possible. If more than one such rectangle exists, it chooses one arbitrarily.

Can we prove a bound on the approximation ratio of this algorithm?


For example, if $M=1,N=6,k=3$ (i.e., we wish to cover a length $6$ line with intervals of size $3$), the optimal (minimizing the number of rectangles in the cover) picks a rectangle covering $[1,2,3]$ and another one covering $[4,5,6]$.

The greedy algorithm, on the other hand, may first choose the interval $3,4,5$, and then proceed with $1,2,3$ and finally $4,5,6$.

The number of rectangles used by the algorithm is $3$, while the optimum is $2$, thus the approximation ratio of the example is $1.5$.

I have a proof that the approximation ratio of the 1D case ($M=1$) is $2$ (and it is tight).

What is the approximation ratio of the general $N\times M$ grid algorithm?


I'm well aware that it is probably possible to solve the problem optimally in linear time with a different algorithm, but in my application the rectangles are generated arbitrarily (e..g, think of a stores who wish to serve as many customers as possible in a grid) and are not ours to choose.

$\endgroup$
  • $\begingroup$ @D.W. - let $x$ be the maximal number of uncovered squared which a rectangle of size $\le k$ may cover.The algorithm may choose any rectangle covering $x$ squares. $\endgroup$ – R B May 24 '15 at 13:17
  • $\begingroup$ @D.W. - I allow $\le k$ rectangles, so if $k=10$, the algorithm may choose a $3\times 3$ square, if it covered as many uncovered squares as possible. $\endgroup$ – R B May 24 '15 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.