Covering a rectangle with dominoes
Difference between en2 and en3, changed 37 character(s)
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 t
he dominoes that weI 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 :)↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English bigintegers 2019-12-04 03:15:33 160
en15 English bigintegers 2019-12-03 06:04:27 86
en14 English bigintegers 2019-12-03 05:55:20 68
en13 English bigintegers 2019-12-03 05:11:33 18
en12 English bigintegers 2019-12-03 05:08:47 130
en11 English bigintegers 2019-12-03 05:03:33 155
en10 English bigintegers 2019-12-03 05:02:17 0 (published)
en9 English bigintegers 2019-12-03 05:02:06 64 (saved to drafts)
en8 English bigintegers 2019-12-03 05:00:54 52
en7 English bigintegers 2019-12-03 05:00:02 9 Tiny change: 'ell as n distinct dominoes ' -> 'ell as n dominoes '
en6 English bigintegers 2019-12-03 04:59:34 118
en5 English bigintegers 2019-12-03 04:58:40 0 (published)
en4 English bigintegers 2019-12-03 04:58:16 55 (saved to drafts)
en3 English bigintegers 2019-12-03 04:56:39 37 (published)
en2 English bigintegers 2019-12-03 04:55:55 49 (saved to drafts)
en1 English bigintegers 2019-12-03 04:55:39 1222 Initial revision (published)