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. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."

         Rectangle Partition http://cs.smith.edu/%7Eorourke/MathOverflow/EppsteinRectangles.jpg

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

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. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."

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

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. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."

         Rectangle Partition http://cs.smith.edu/%7Eorourke/MathOverflow/EppsteinRectangles.jpg

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

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. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."

         Rectangle Partition http://cs.smith.edu/%7Eorourke/MathOverflow/EppsteinRectangles.jpg

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