1
$\begingroup$

Given a large rectangle and a set $S$ of small rectangles each with a value $v_i$. My problem is to find a collection of rectangles $T\subseteq S$ to put in the large rectangle so as to maximize the overall value $\sum_{i\in T}v_i$, subject to the constraint that the selected small rectangles cannot overlap with each other.

I suppose the problem is NP-hard. Can we design an approximation algorithm (PTAS or constant-factor approximation ratio) approaching the optimum?

$\endgroup$
1
1
$\begingroup$

This problem is known as maximum disjoint set. In your case, assuming the rectangles are parallel to the axes, the problem is maximum disjoint set for axis-parallel rectangles. The problem is indeed NP-hard, but Wikipedia has an approximation algorithm with an approximation ratio of $O(\log \log n)$ if all values $v_i$ are the same, or approximation ratio $O(\log n/\log \log n)$ for the general case where the values may differ for each rectangle. You can check out the citations there to find an entry point to the research literature.

I have not been able to find any lower bounds on what approximation ratio is achievable, so as far as I can tell, it is an open problem whether you can achieve a constant-factor approximation ratio for this problem.

If you're willing to relax the running time requirement, there is a recent result achieving an approximation ratio $1+\epsilon$, at the cost that the running time becomes larger than polynomial, namely, $2^{\text{poly}(\log \log n/\epsilon)}$. See arXiv:1307.1774 and arXiv:1608.0027.

In the case where none of the small rectangles are too small (i.e., each small rectangle has an edge whose length is at least a constant fraction of the length of corresponding edge of the large rectangle), this problem has a PTAS, i.e., $1+\epsilon$ approximation ratio is achievable. See arXiv:1703.04758.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.