An _exact_ partition into the minimum number of rectangles can be found in $O(n^{3/2} \log n)$ time,
if the set $S$ forms a region with $n$ corners.
See David Eppstein's survey, "Graph-Theoretic Solutions to Computational Geometry Problems," [arXiv:0908.3916][1].
For primary references, see his answer to the earlier MO question, "[split polygon into minimum amount of rectangles and triangles][2]."

<hr />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
![Rectangle Partition][3]<hr />

Because there is a fast exact algorithm, perhaps there has not been study of approximation algorithms.


  [1]: http://arxiv.org/abs/0908.3916
  [2]: https://mathoverflow.net/questions/28303/
  [3]: https://i.sstatic.net/3eGzF.jpg