On Approximating the Rate Region for Source Coding with Coded Side Information

The achievable rate region for the problem of lossless source coding with coded side information was derived by Ahlswede and Korner in 1975. While the Ahlswede-Korner bound completely characterizes the achievable rate region when the source and side information are memoryless, calculating this bound for a given memoryless joint probability mass function on the source and side information requires an optimization over all possible auxiliary random variables meeting a given Markov condition and alphabet size constraint. This optimization turns out to be surprisingly difficult even for very simple distributions on the source and side information. We here propose a (1 + epsiv)-approximation algorithm for the given rate region. The proposed technique involves quantization of a space of conditional distributions followed by linear programming. The resulting algorithm guarantees performance within a multiplicative factor (1 + epsiv) of the optimal performance - even when that optimal performance is unknown.