So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of polyominos $p_1, p_2, ..., p_n$ (not necessarily distinct), and we want to find a tiling of a rectangle of dimension $a \times b$ with $a, b \leq n$ that maximizes the number of squares covered, where we can use each $p_i$ at most once, and polyominos must be fully contained within the rectangle. Now, we have the decision problem which tells us, for a given $t$, if there is some tiling covering at least $t$ squares, and the optimization problem which is finding a tiling that covers the maximum number of squares.
There are two parts: first, if you can solve the optimization problem in polynomial time, can you solve the decision problem in polynomial time? And secondly, if you can solve the decision problem in polynomial problem, can you solve the optimization problem in polynomial time?
The first part is easy, for if we have an oracle that solves the optimization in polynomial time, solving the decision problem in polynomial time is obvious.
However, given an oracle for the decision problem, I was unable to find a way to solve the optimization problem in polynomial time. The main issue I'm facing is that the decision oracle only works for rectangular boards, which means we can't just place pieces and then use the oracle to see if the placement works, since we won't have a rectangular board if we want to exclude the piece we just placed. It isn't hard to determine the actual maximum number of tiles you can cover, and you can even find the actual pieces you need to use, but I haven't been able to figure out a way to find an arrangement of the pieces in polynomial time using the oracle. I assume there is some trick here, but I don't see it.
Here are some more details. A similar problem can be found here, so to address the commenter's question a priori we sort of hope that this problem can be solved using the decision oracle. However, there is only one difficulty with adapting this approach which makes it seem fruitless:
- The oracle in the linked question is in a sense stronger because it works on any graph. In particular we can encode the notion of coloring using a modified graph. In this sense the oracle of this problem is much, much weaker since it only works on rectangular boards.