Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?
In one form, your question is actually a clustering question that is addressed by the information bottleneck method. 

Roughly, $Y$ represents the rows of a joint distribution and $X$ represents the columns. The random variable $Z$ then represents a distribution over the rows ($Y$) that is highly compressed (because $I(Z;Y)$ is small) but represents the joint distribution well (because $I(Z;X)$ is large). 

It's not clear to me that this can be solved using LPs. the underlying problem is not convex. But there's a simple EM-style alternating optimization scheme that can be used to solve it.