The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs–Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature T) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins).When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths and require the inversion of an n × n matrix with n being the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy (T → 0+) and the solution to the corresponding electrical circuit (T → ∞). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.

We consider random i.i.d. samples of absolutely continuous measures on bounded connected domains. We prove an upper bound on the $\infty $-transportation distance between the measure and the empirical measure of the sample. The bound is optimal in terms of scaling with the number of sample points.

We study a form of optimal transportation surplus functions which arise in hedonicpricing models. We derive a formula for the Ma–Trudinger–Wang curvature of thesefunctions, yielding necessary and sufficient conditions for them to satisfy(A3w). We use this to give explicit new examples of surplus functionssatisfying (A3w), of the formb(x,y) = H(x + y)where H is a convex function on ℝn. We alsoshow that the distribution of equilibrium contracts in this hedonic pricing model isabsolutely continuous with respect to Lebesgue measure, implying that buyers are fullyseparated by the contracts they sign, a result of potential economic interest.

Given the probability measure ν over the given region $\Omega\subset \mathbb{R}^n$ , we consider the optimal location of a setΣ composed by n points in Ω in order to minimize theaverage distance $\Sigma\mapsto \int_\Omega \mathrm{dist}\,(x,\Sigma)\,{\rm d}\nu$ (theclassical optimal facility location problem). The paper compares twostrategies to find optimal configurations: the long-term one whichconsists in placing all n points at once in an optimal position, and the short-term one which consists in placing the points one by one addingat each step at most one point and preserving the configurationbuilt at previous steps. We show that the respective optimizationproblems exhibit qualitatively different asymptotic behavior as $n\to\infty$ , although the optimization costs in both cases have the same asymptotic orders of vanishing.

Among ${\mathbb R}^3$ -valued triples of random vectors (X,Y,Z) having fixed marginal probability laws, what is the best way to jointly draw (X,Y,Z) in such a way that the simplex generated by (X,Y,Z) has maximal average volume? Motivated by this simple question, we study optimal transportation problems with several marginals when the objective function is the determinant or its absolute value.

We introduce and analyse a mixed formulation of theMonge-Kantorovich equations, which express optimality conditions forthe mass transportation problem with cost proportional to distance.Furthermore, we introduce and analyse the finite elementapproximation of this formulation using the lowest orderRaviart-Thomas element. Finally, we present some numericalexperiments, where both the optimal transport density and theassociated Kantorovich potential are computed for a coupling problemand problems involving obstacles and regions of cheaptransportation.

Given two measured spaces $(X,\mu)$ and $(Y,\nu)$ , and a third space Z,given two functions u(x,z) and v(x,z), we study the problem of finding twomaps $s:X\rightarrow Z$ and $t:Y\rightarrow Z$ such that the images $s(\mu)$ and $t(\nu)$ coincide, and the integral $\int_{X}u(x,s(x))d\mu-\int_{Y}v(y,t(y))d\nu$ is maximal. We give condition on u and v for whichthere is a unique solution.

A multiphase generalization of the Monge–Kantorovich optimaltransportation problem is addressed. Existence of optimal solutions is established.The optimality equations are related to classical Electrodynamics.