For the Kantorovich-Rubinstein theorem, please see the wikipedia page http://en.wikipedia.org/wiki/Wasserstein_metric (which does not contain a reference for the proof).
I am only interested in the case of discrete distributions; that is, $\mu, \nu$ are measures on the real line supported on finite sets. I believe that there should be a simple combinatorial proof of the Kantorovich theorem in this setting. Any references? If someone can at least sketch the proof, it will be even better.