As a part of a computer science algorithms research project, I am troubled with the following problem:
Given an l x w rectangle, where 1 <= l, w <= n as well as n distinct dominoes d1, d2, d3, ..., dn (each domino has a different length and width), I want to cover as much of the l x w rectangle as possible using the given dominoes with different dimensions. Now the dominoes that I place into the rectangle don't need to be small enough to fit inside of the rectangle, so it doesn't actually matter if part of a domino is hanging out of the rectangle.
Now suppose I have a polynomial algorithm that does the following:
Given the list of domino dimensions and the board size and a value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and false otherwise. Let's say this algorithm runs in O(n^k) time.
Now using this algorithm, is it possible to find a tiling of the a x b rectangle that covers as many squares as possible (i.e. a maximal orientation) How fast?
I think the answer is no right now but I just can't think of it so that's my reason. Maybe someone smarter than me can think of something :)