Exact solutions to the transportation problem on the line

Given distributions mu of production and nu of consumption on the line, the Monge-Kantorovich problem is to decide which producer should supply each c onsumer in order to minimize the total transportation costs. Here cost will be assumed to be a strictly concave function of the distance, which transl ates into an economy of scale for longer trips and may encourage cross-haul ing. The resulting solutions display a hierarchical structure that reflects a striking separation into local and global scales also found in the real world. Moreover, this structure can be exploited to reduce the infinite-dim ensional linear problem to a convex minimization in m variables, where 2m+2 counts the number of times that mu-nu changes sign. A combinatorial algori thm is then derived which yields exact solutions by optimizing a certain fi nite sequence of convex, separable network flows.