5
$\begingroup$

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:

  1. 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.
$\endgroup$
  • $\begingroup$ Do you know that a polynomial time solution exists? $\endgroup$ – Throckmorton Dec 4 '19 at 2:45
  • $\begingroup$ I was told that a polynomial time reduction does exist, supposedly, but not what it is. And it does seem like there should be a reduction (since ones exist for problems that seem reasonably similar), but the rectangular board restriction makes it seemingly much more difficult. $\endgroup$ – tradewinds Dec 4 '19 at 17:15
3
$\begingroup$

Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.

A gangly polyomino in a double-width problem instance

Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \times (b+1)$ in which each polyomino's width has been doubled, and a new polyomino has been added that consists of a row of $2a+1$ blocks with a column of $b$ blocks hanging below its leftmost block (thus giving it a total height of $b+1$) and a double-width copy of polyomino $p_1$ (the template polyomino) below the top row and to the right of the left column but pushed up and left as far as it will go, so that at least one block of column 2 below row 1 is occupied, and at least one block of row 2 to the right of column 1 is occupied. Intuitively, because all other polyominos have even width, the only way to fill up the odd-width rectangle we have is to use this gangly new polyomino, in which case its horizontal and vertical "arms" must form the topmost row and leftmost column, respectively.

Let the size of an optimal solution to the original problem be $k$ (this can be found in $O(\log {ab})$ time with binary search using only decision problem oracle calls). Iff there is a solution to the newly constructed decision problem instance with size $2k+(2a+1)+(b+1) = 2(k+a)+b+2$, then there is a solution to the original instance that has $p_1$ in its top-left corner.

If the answer is "no", try the same instance again but with a different template polyomino: form the gangly polyomino by pressing $p_2$ into the top-left corner instead of $p_1$. Repeat this until you find you hit a "yes" instance. If none of the polyominos results in a "yes" instance when pressed into the top-left corner, start again with $p_1$ but one block down from where it was in the first constructed problem, and with the blocks at positions $(2, 2)$ and $(2, 3)$ also filled in. Why? These represents a (double-width) block that we know must remain empty in every optimal solution (since if there was some optimal solution where it was covered by a polyomino, we would have found it by now). Add 2 to the target value for the decision problem to compensate for the added filler blocks.

If performing this down-one-row move would cause the polyomino to extend past the bottom of the range, add the 2 filler blocks as usual but instead move the template polyomino back up to the top (so that its topmost block occupies row 2) and as far left as possible so as to not overlap any existing block.

In general, a constructed instance with $f$ filler blocks gets $f$ added to its decision problem target.

Once you hit a "yes" instance, you know that this placement of the template polyomino is part of some optimal solution, so you keep that placement of the template in the gangly polyomino from that point on. Form the next problem with the next available polyomino as template immediately below the last one, or flush with the top and to the right as usual.

Time complexity

Each time we try all $n$ polyominos at some position, we add at least 2 blocks (either 2 filler blocks, or the double-width blocks corresponding to some input polyomino) to the gangly polyomino. We can only add at most $ab$ such pairs of blocks before it is no longer possible to obtain a "yes" answer, so at most $abn$ calls to the decision oracle suffice.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think I see the general idea, but I have a few questions. How do we know that $2k$ is the optimal solution for the tiling for the rectangle of double width? Also, I think I forgot to specify that the oracle only accepts problems where $a, b \leq n$. For the problem of double width, how would we accommodate this restriction? Do we just pad the list of polyominos with garbage ones (to increase the size of $n$)? $\endgroup$ – tradewinds Dec 5 '19 at 2:08
  • 1
    $\begingroup$ If there's a solution of size $k$ to an $a\times b$ problem instance, then there's a solution of size $2k$ to a $2a\times b$ problem that uses the same set of polyominos but with their width doubled -- just double everything horizontally. If you increase the width further by 1, this solution of size $2k$ still exists; also, for whatever polyomino $p$ is in the top-left position in the solution to the original problem, when we make the $(2a+1)\times b$ instance that uses $p$ as the template for the gangly polyomino, then a solution of size $2k+2a+1+b+1$ exists. That's the easy direction. $\endgroup$ – j_random_hacker Dec 5 '19 at 8:20
  • 1
    $\begingroup$ The other direction (that a solution of size $2k+2a+1+b+1$ to the constructed instance implies a solution of size $k$ using the template polyomino in a particular position) is harder, and it might be that it doesn't actually work, but here is a fix that definitely does: If $b$ is even, increase the height of each constructed instance, and the "thickness" of the gangly polyomino's horizontal arm, by 1, and also increase the target size by $2a+1$, so that we always wind up with an odd target size. ... $\endgroup$ – j_random_hacker Dec 5 '19 at 8:39
  • 1
    $\begingroup$ ... If this odd target size is the largest size that can be reached (2 oracle calls), then every optimal solution uses the gangly polynomial since there's no way to reach an odd total size using just the remaining polyominos, which are all even-sized. Then we know that we can remove the gangly polynomial's two arms, leaving just its doubled template subpart, and divide the width by 2 to get an optimal solution to the original problem that includes that placement of the template. $\endgroup$ – j_random_hacker Dec 5 '19 at 8:40
  • 1
    $\begingroup$ Is the $(2a+1) \times b$ problem instance supposed to be a $(2a+1) \times (b+1)$ problem instance (per your original comment)? So we should be considering when $(b+1)$ is even rather than when $b$ is even? $\endgroup$ – tradewinds Dec 5 '19 at 14:56

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.