Minimum-area orthogonal rectangle coverage
See the paper by Aronov, Ezra and Sharir. They handle the case for points. For rectangles it is not even immediately obvious that an LP relaxion is easy to do, since there might be a chaining effect, and as such the number of candidate rectangles might be large (i.e., $O(n^k)$). 

A solution with $O(k \log k)$ rectangles with the same area as the optimal solution, should follow by using BSP (binary space partition) and dynamic programming in polynomial time. So searching on the web would give you refs to papers using this scheme (I dont remember the ref, sorry). 

http://www.cims.nyu.edu/~esther/Publications/AronovEzraSharir.pdf