A decomposition theorem for balanced measures

Abstract

Let $G=(V,E)$ be a connected graph. A probability measure $\hat{I}¼$ on $V$ is called "balanced" if it has the following property: if $T_{\hat{I}}¼(v)$ denotes the "earth mover's" cost of transporting all the mass of $\hat{I}¼$ from all over the graph to the vertex $v$, then $T_{\hat{I}}¼$ attains its global maximum at each point in the support of $\hat{I}¼$. We prove a decomposition result that characterizes balanced measures as convex combinations of suitable "extremal" balanced measures that we call "basic." An upper bound on the number of basic balanced measures on $G$ follows, and an example shows that this estimate is essentially sharp.

Published in Discrete Mathematics