Finding an efficient optimal partial tiling algorithm is still an open
problem. We have worked on a special case, the tiling of Manhattan polyominoes
with dominoes, for which we give an algorithm linear in the number of columns.
Some techniques are borrowed from traditional graph optimisation problems.