1. Introduction

This paper introduces some PDE and ODE methods for constructively solving one

version of the Monge-Kantorovich mass transfer problem.

The basic issue is this. Given two nonnegative, summable functions / ± on E n satisfying

the mass balance condition

/ f+dx= f f-dy, (1.1)

we consider the corresponding measures ^ + = f+dx, f.t~ = f~dy, and ask how we can

optimally rearrange /x+ onto \x~. If r : Rn —» Rn is a smooth, orientation-preserving, one-to-

one mapping, the requirement is that r transfer fi+ onto /i"; that is,

/+(x) = /"(r(x)) detDr{x) (x € E n ). (1.2)

Denote by A the admissible class of smooth, one-to-one functions r satisfying (1.2). We then

seek a mass transfer plan s £ A which is optimal in the sense that

/[s] = min/[r], (1.3)

reA

where

I[r]= f \x-r{x)\f+(x) dx= [ \x - r(x)|d/x+ . (1.4)

This is a form of Monge's problem of the "deblais" and "remblais" (cf. Monge [M],

Dupin [D], Appell [A]), dating from the early 1780's. The physical interpretation is that

we are given a pile of soil or rubble (the "deblais"), with mass density / + , which we wish

to transport to an excavation or fill (the "remblais"), with mass density / " . For a given

transport scheme r, condition (1.2) is conservation of mass. Furthermore, as each particle

of soil moves a distance \x — r(x)\, we can interpret I[r] as the total work involved. We

consequently are looking for a way to rearrange /i + = f+dx onto \T = f~dy, which requires

the least work.

This optimization problem, and its many, many variants and extensions (entailing for

example more general measures on more general spaces, different cost functionals, etc.)

has been intensively studied for over two hundred years. We review some of the principal

discoveries.

a. Monge. Monge himself contributed the essential insight that an optimal transfer plan

s should be in part determined by a potential u. More precisely, he deduced by heutistic,

°L.C.E. is supported in part by NSF Grant DMS-94-24342, and W.G. is supported in part by NSF

Grant DMS-96-22734.

Received by the editor May 1, 1996; and in revised form February 19, 1997.

1