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. T with different dimensions. ↵
Now the dominoes thatweI 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 :)↵
↵
↵
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
Now the dominoes that
↵
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 :)↵
↵