Exact solutions to the transportation problem on the line

Given distributions ;w of production and v of consumption on the line, the Monge–Kantorovich problem is to decide which producer should supply each consumer in order to minimize the total transportation costs. Here cost will be assumed to be a strictly concave function of the distance, which translates into an economy of scale for longer trips and may encourage cross–hauling. 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–dimensional linear problem to a convex minimization in m variables, where 2m + 2 counts the number of times that ;w–v changes sign. A combinatorial algorithm is then derived which yields exact solutions by optimizing a certain finite sequence of convex, separable network flows.