We derive new algorithms for approximating the rate regions for a family of source coding problems that includes lossy source coding, lossy source coding with uncoded side information at the receiver (the Wyner-Ziv problem), and an achievability bound for lossy source coding with coded side information at the receiver. The new algorithms generalize a recent approximation algorithm by Gu and Effros from lossless to lossy coding. In each case, prior information theoretic descriptions of the desired regions are available but difficult to evaluate for example sources due to their dependence on auxiliary random variables. Our algorithm builds a linear program whose solution is no less than the desired lower bound and no greater than (1 +∈) times that optimal value. These guarantees are met even when the optimal value is unknown. Here ∈ > 0 is a parameter chosen by the user; the algorithmic complexity grows as O(∈-M) as ∈ approaches 0, where M > 4 is a constant that depends on the source coding problem and the alphabet sizes of the sources. © 2008 IEEE.