${\mathcal {W}}_\infty$-transport with discrete target as a combinatorial matching problem

Abstract

In this short note, we show that given a cost function c, any coupling $\pi$ of two probability measures where the second is a discrete measure can be associated to a certain bipartite graph containing a perfect matching, based on the value of the infinity transport cost $\Vert c \Vert _{L^\infty (\pi )}$. This correspondence between couplings and bipartite graphs is explicitly constructed. We give two applications of this result to the ${\mathcal {W}}_\infty$ optimal transport problem when the target measure is discrete, the first is a condition to ensure existence of an optimal plan induced by a mapping, and the second is a numerical approach to approximating optimal plans.

1 Introduction

1.1 Statement of the problem

In this paper, we relate the ${\mathcal {W}}_\infty$-optimal transport problem to a combinatorial matching problem in the case where the target measure is discrete. Our main result is valid for any source measure, in particular one which may not be absolutely continuous. As applications, we first obtain a condition ensuring that there exists an optimal plan induced by a mapping, and second, a numerical method to approximate optimal plans in the ${\mathcal {W}}_\infty$-transport problem, which gives the first numerical algorithm for this problem. In this paper, a discrete measure will always refer to a finite linear combination of delta measures.

We recall the problem as follows. Let $(X, \mu )$ be an arbitrary probability measure space, and $Y = \{y_1, \dots , y_N \}$ be a finite set. We fix some probability measure $\nu$ whose support is equal to Y and some function $c: X\times Y \rightarrow \mathbb {R}$ that is measurable with respect to the product $\sigma$-algebra. Additionally, we write $\Pi (\mu , \nu )$ for the collection of probability measures on $X\times Y$ whose left and right marginals equal $\mu$ and $\nu$ respectively. Then the ${\mathcal {W}}_\infty$-optimal transport problem is to find some $\pi \in \Pi (\mu , \nu )$ so that

$$\begin{aligned} {\mathcal {W}}^c_\infty (\mu , \nu ):=\Vert c \Vert _{L^\infty (\pi )} = \inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })}. \end{aligned}$$

(1.1)

Any $\pi \in \Pi (\mu , \nu )$ is referred to as a transport plan and a minimizing $\pi$ is referred to as a ${\mathcal {W}}_\infty$-optimal transport plan. We also say that $\Vert c \Vert _{L^\infty (\pi )}$ is the $\infty$-transport cost of the transport plan $\pi$.

Additionally, if a transport plan $\pi$ is of the form $({{\,\mathrm{Id}\,}}\times T)_\# \mu$ for some measurable map $T: X\rightarrow Y$, then the map T is called a transport map and $\pi$ is induced by T.

1.2 Main results

We will show that the existence of a transport plan (not necessarily optimal) with some transport cost can be characterized by finding a perfect matching in a certain bipartite graph, built using the source and target measures $\mu$ and $\nu$. We start with some definitions.

Definition 1.1

In this paper, a bipartite graph G will refer to a graph with (non-negatively) weighted vertices and unweighted simple edges, which is such that the vertex set can be divided into two disjoint sets L and R (the left and right vertex sets), and all edges connect exactly one vertex in L with one vertex in R.

We refer to $V := L \coprod R$ (the disjoint union) as the vertex set. For any $v \in V$, we use w(v) to denote the weight of the vertex v.

Furthermore, given any subset $S \subset V$, we use $\Gamma (S)$ to denote the neighbors of S, i.e. $\Gamma (S)$ is the collection of all $v \in V$ so that there exists $\tilde{v} \in S$ such that there is an edge between v and $\tilde{v}$.

Definition 1.2

Given a bipartite graph G, a matching is a map $M: L \times R \rightarrow [0, \infty )$. A matching is said to be valid if it satisfies the following two conditions.

• 1. For any $l \in L$ and $r \in R$, $M(l,r) = 0$ unless there is an edge between l and r.

• 2. $\sum _{r' \in R} M(l,r') \le w(l)$ and $\sum _{l' \in L} M(l',r) \le w(r)$ for all $l\in L$ and $r\in R$.

Finally we say that a matching is perfect if $\sum _{r' \in R} M(l,r') = w(l)$ and $\sum _{l' \in L} M(l',r) = w(r)$ for all $l\in L$ and $r\in R$.

Definition 1.3

A transport graph is a bipartite graph where $L = 2^Y$ and $R = Y$, and there is an edge between $l \in L$ and $r \in R$ if and only if $r \in l$. Furthermore, we require that the weights of vertices in L and R respectively sum to 1.

For any $\omega \in \mathbb {R}$, the $\omega$-transport graph, denoted $G_\omega$, is a transport graph where the vertex weights for any $y\in Y$ and $A\in 2^Y$ are defined by

$$\begin{aligned} w(y)&=\nu (\{y\}),\\ w(A)&=\mu (X_A), \end{aligned}$$

where

$$\begin{aligned} X_A := \bigcap _{y\in A} \{x\in X\mid c(x,y) \le \omega \} \cap \bigcap _{y \not \in A} \{x\in X\mid c(x,y) > \omega \}. \end{aligned}$$

(1.2)

Remark 1.4

We remark that any bipartite graph can be made into a transport graph by labeling the left hand vertices with its collection of neighbors and adding zero weight left vertices for any remaining subsets. Note that in a transport graph, if M is a valid matching, then $\sum _{r' \in R} M(l,r') = w(l)$ for all $l\in L$ if and only if $\sum _{l' \in L} M(l',r) = w(r)$ for all $r\in R$; in particular, either condition implies that M is perfect.

With this terminology in hand, we can state our main result.

Theorem 1.5

Let $\mu \in {\mathcal {P}}(X)$ and $\nu$ be a discrete measure whose support is the finite set Y. Then there exists a transport plan $\pi \in \Pi (\mu , \nu )$ with $\infty$-transport cost at most $\omega$ if and only if the $\omega$-transport graph $G_\omega$ has a perfect matching. Furthermore, if $\mu$ has no atoms and $G_\omega$ has a perfect matching for some $\omega$, such a corresponding transport plan can be taken to arise from a transport map.

We note that the proof of the theorem gives explicit constructions of a transport plan/perfect matching arising from this correspondence (see (2.1) and (2.2)). Finally, it is a simple matter to obtain the following useful corollary.

Corollary 1.6

If $\mu$ has no atoms, then for any ${\mathcal {W}}_\infty$-optimal transport plan $\pi$, there exists a transport map T such that $({{\,\mathrm{Id}\,}}\times T)_\#\mu$ has the same $\infty$-transport cost as $\pi$.

In Section 2 below, we give the proofs of these main results, Theorem 1.5 and Corollary 1.6.

One interesting observation we can make is that any bipartite graph can be suitably modified, and realized as the $\omega$-transport graph for a certain ${\mathcal {W}}_\infty$-optimal transport problem. Since Theorem 1.5 gives an explicit method to construct transport plans from $\omega$-transport graphs and vice-versa, this shows that solving the ${\mathcal {W}}_\infty$-transport problem is equivalent to solving the matching problem for an arbitrary bipartite graph. This will be explored in Section 3.

Finally we propose an application of Theorem 1.5 in order to numerically find approximations of ${\mathcal {W}}_\infty$-optimal transport plans. The idea is the following. Fix a desired error tolerance $\epsilon >0$. Then for any $\omega \in ({\mathcal {W}}_\infty (\mu , \nu ), {\mathcal {W}}_\infty (\mu , \nu )+\epsilon ]$, by Theorem 1.5, there exists a perfect matching in the corresponding $\omega$-transport graph. If it is possible to find this matching, then we can obtain a transport plan via (2.2) whose $\infty$-transport cost is less than $\epsilon$ plus the optimal (minimal) value. This can be exploited as there are well established numerical methods to find a perfect matching in a bipartite graph if the existence of such a matching is known. In practice, since the actual optimal value ${\mathcal {W}}_\infty (\mu , \nu )$ is unknown, it is necessary to start with a sufficiently large interval and iteratively do interval halving. In Section 4, we set out the numerical algorithm, and present some empirical examples.

1.3 Literature review

The ${\mathcal {W}}_\infty$-problem has appeared in a number of applications, we give a non-exhaustive review of a few examples. The problem was first considered by McCann (see [9]) to analyze a variation formulation for the problem of rotating binary stars. It was later considered by Carrillo, Gualdani, and Toscani in porous medium flow to bound growth of the wetted region ([4]). Finally, ${\mathcal {W}}_\infty$-transport has recently appeared in quantitative convergence of empirical measures, and of Gromov-Hausdorff convergence of discrete geometric structures to the smooth one on the torus ([10, 11]).

Theoretical aspects of the ${\mathcal {W}}_{\infty }$-problem for cost given by a power of the Euclidean distance are treated in [3]. There the authors introduce the notion of infinitely cyclical monotonicity, and show that this condition characterizes the class of restrictable solutions in the ${\mathcal {W}}_\infty$-problem, this is generalized in [7] to other cost functions. Additionally, it is shown that if the source measure $\mu$ gives no mass to $n-1$ dimensional Lipschitz sets, and with some mild conditions on c, an optimal plan that is infinitely cyclically monotone is induced by a transport map ([7, Theorem 3.5]). Our result Corollary 1.6 states that under the weaker assumption that $\mu$ has no atoms, and for an arbitrary cost function c, if there exists an optimal plan, then there also exists an optimal plan, induced by a map; however note that we do not claim any kind of uniqueness. A dual problem is also treated in [1]; our methods in this paper use neither duality, nor the notion of infinitely cyclical monotonicity; we plan to investigate our result in the context of restrictable solutions in a future work.

One possible idea for a numerical method could be to solve the optimal transport problem for cost functions of the form $c(x, y)^p$ and take a limit as $p\rightarrow \infty$ with the hope of obtaining a solution of the $\infty$-transport problem. However, this idea is unfortunately too naive to yield an effective algorithm. Except when both $\mu$ and $\nu$ are discrete measures, the only numerical methods for optimal transport with general cost functions that also come with proven bounds require extra structure of the cost function (the main one being the Ma-Trudinger-Wang or A3 condition related to regularity of the Monge-Ampère equation, as introduced in [8]). This condition is quite rigid and is unlikely to hold for costs $c(x, y)^p$ for arbitrary p: for example, the Ma-Trudinger-Wang condition fails to hold for $|x-y|^p$ when p is positive, unless $p=2$. Admittedly our proposed method has rather large performance bounds as it is based on a direct subset search, however it is still the first and currently only numerical approach to the $\infty$-transport problem with provable bounds.

2 Proofs of main results

In this section, we fix an $\omega \in \mathbb {R}$, and take the sets $X_A$ as in (1.2). We first show a basic partitioning property of the $X_A$.

Lemma 2.1

The collection $\{X_A\}_{A\in 2^Y}$ is a disjoint partition of X, i.e. $X_A \cap X_B = \emptyset$ if $A \ne B$ and $X = \bigcup _{A \in 2^Y} X_A$.

Proof

Fix some $A, B \subset Y$ so that $A \ne B$, then without loss of generality there exists $y \in A$ so that $y \not \in B$. Then by definition, $X_A \subset \{x\in X\mid c(x,y) \le \omega \}$ and $X_B \subset \{x\in X\mid c(x,y) > \omega \}$ but clearly $\{x\in X\mid c(x,y) \le \omega \} \cap \{x\in X\mid c(x,y) > \omega \} = \emptyset$. Hence $X_A$ and $X_B$ are disjoint.

Next to see that the $X_A$ cover X, pick any $x \in X$. We define $A:=\{y \in Y\mid c(x,y) \le \omega \}$, it is then easily seen that $x \in X_A$, even if $A=\emptyset$. $\square$

Proof of Theorem 1.5

Let $G_\omega$ be the associated $\omega$-transport graph defined using the sets $X_A$, $\mu$, and $\nu$ as in Definition 1.3. Recall that we write $L = 2^Y$ and $R = Y$ for the left and right vertex sets of $G_\omega$.

First let $\pi$ be a transport plan satisfying $\Vert c \Vert _{L^\infty (\pi )} \le \omega$. Then we can define the matching M by setting

$$\begin{aligned} M(A, y) = \pi (X_A \times \{y\}) \end{aligned}$$

(2.1)

for any $A \in L$ and $y \in R$.

We show that M is a perfect matching. First, if $M(A, y) =\pi (X_A \times \{y\}) > 0$, there exists an $x \in X_A$ so that $c(x, y) \le \Vert c \Vert _{L^\infty (\pi )} \le \omega$. We conclude that $y \in A$, as, if $y \not \in A$, we would have $X_A \subset \{\tilde{x}\in X\mid c(\tilde{x},y) > \omega \}$. In particular, there is an edge between A and y in $G_\omega$.

Next

$$\begin{aligned} \sum _{A \in L} M(A, y) = \sum _{A \in L} \pi (X_A \times \{y\}) = \pi (\bigcup _{A \in L} X_A \times \{y\}) = \pi (X \times \{y\}) = w(y) \end{aligned}$$

where we have used Lemma 2.1 for the middle two equalities. We also see

$$\begin{aligned} \sum _{y \in R} M(A, y) = \sum _{y \in R} \pi (X_A \times \{y\}) = \pi (X_A \times \bigcup _{y \in R} \{y\}) = \pi (X_A \times Y) = \mu (X_A) = w(A). \end{aligned}$$

This completes the proof that M is a perfect matching.

Next suppose that we are given a perfect matching M in $G_\omega$. We want to construct a transport plan. Note that by Lemma 2.1, the collection $\{X_A \times \{y\}\}_{(A, y)\in L\times R}$ forms a partition of $X \times Y$. Define $\pi \in {\mathcal {P}}(X\times Y)$ as follows. If $\mu (X_A) = 0$, we set $\pi \big |_{X_A \times \{y\}} \equiv 0$. Otherwise we set

$$\begin{aligned} \pi \bigg |_{X_A \times \{y\}} := \frac{M(A, y)}{\mu (X_A)\nu (\{y\})} \left( \mu \bigg |_{X_A} \otimes \nu \bigg |_{\{y\}}\right) , \end{aligned}$$

(2.2)

in other words, for $S \subset X \times Y$, we have

$$\begin{aligned} \pi (S) = \sum _{\{A\in 2^Y\mid \mu (X_A) > 0 \}} \sum _{y\in Y}\frac{M(A, y)}{\mu (X_A)\nu (\{y\})} (\mu \big |_{X_A} \otimes \nu \big |_{\{y\}})(S). \end{aligned}$$

(2.3)

Note that for any measurable $Q \subset X$,

$$\begin{aligned} \pi (Q \times Y)&= \sum _{\{A\in 2^Y\mid \mu (X_A)> 0 \}} \sum _{y\in Y} \frac{M(A, y)}{\mu (X_A)\nu (\{y\})} (\mu \big |_{X_A} \otimes \nu \big |_{\{y\}})(Q \times Y) \\&= \sum _{\{A\in 2^Y\mid \mu (X_A)> 0 \}} \sum _{y\in Y}\frac{M(A, y)}{\mu (X_A)\nu (\{y\})} \mu (X_A \cap Q) \nu (\{y\})\\&= \sum _{\{A\in 2^Y\mid \mu (X_A)> 0 \}} \frac{\mu (X_A \cap Q)}{\mu (X_A)} \sum _{y\in Y} M(A, y) \\&= \sum _{\{A\in 2^Y\mid \mu (X_A)> 0 \}} \frac{\mu (X_A \cap Q)}{\mu (X_A)} \mu (X_A) \\&= \sum _{\{A\in 2^Y\mid \mu (X_A) > 0 \}} {\mu (X_A \cap Q)} = \mu (Q) \end{aligned}$$

where we have used that M is a perfect matching in order to obtain that $\sum _{y\in Y} M(A, y) = \sum _{y\in R} M(A, y)=w(A)=\mu (X_A)$. Next for any $B \subset Y$,

$$\begin{aligned} \pi (X \times B)&= \sum _{\{A \in 2^Y\mid \mu (X_A)> 0\}} \sum _{y\in Y} \frac{M(A, y)}{\mu (X_A)\nu (\{y\})} (\mu \big |_{X_A} \otimes \nu \big |_{\{y\}})(X \times B) \\&= \sum _{\{A \in 2^Y\mid \mu (X_A)> 0\}} \sum _{y\in Y} \frac{M(A, y)}{\mu (X_A)\nu (\{y\})} \mu (X_A) \nu (B \cap \{y\}) \\&= \sum _{y\in Y} \frac{\nu (B \cap \{y\}) }{\nu (\{y\})} \sum _{\{A \in 2^Y\mid \mu (X_A) > 0\}} M(A, y) \\&= \sum _{y\in Y} \frac{\nu (B \cap \{y\}) }{\nu (\{y\})} \nu (\{y\})= \nu (B) \end{aligned}$$

where we have again used that M is a perfect matching. This shows $\pi \in \Pi (\mu , \nu )$. All that is left to do is to verify that $\Vert c \Vert _{L^\infty (\pi )} \le \omega$. Note that this is the same as saying that $\pi (\{(\tilde{x}, \tilde{y})\in X\times Y \mid c(\tilde{x}, \tilde{y}) > \omega \}) = 0$. Since $\{X_A \times \{ y \}\}_{(A, y)\in L\times R}$ forms a partition of $X \times Y$, it suffices to show that $\pi ((X_A \times \{ y \}) \cap \{(\tilde{x}, \tilde{y}) \in X\times Y\mid c(\tilde{x}, \tilde{y}) > \omega \}) = 0$ for any $(A, y)\in L\times R$.

We consider two cases. First, if $M(A,y) = 0$, then, by definition, we have $\pi (X_A \times \{y\}) = 0$ and so of course $\pi ((X_A \times \{ y \} )\cap \{(\tilde{x}, \tilde{y}) \in X\times Y\mid c(\tilde{x}, \tilde{y}) > \omega \}) = 0$. Second, if $M(A,y) > 0$, then, since M is a perfect matching, we must have $y \in A$. Hence for every $x \in X_A$, we have $c(x,y) \le \omega$, in other words, $X_A \cap \{\tilde{x}\in X\mid c(\tilde{x}, y) > \omega \} = \emptyset$ and so

$$\begin{aligned}&\pi ((X_A \times \{y\})\cap \{(\tilde{x}, \tilde{y})\in X\times Y\mid c(\tilde{x}, \tilde{y})> \omega \}) \\&\quad \le \pi ((X_A \cap \{\tilde{x}\in X\mid c(\tilde{x}, y) > \omega \}) \times \{y\}) )=0 \end{aligned}$$

as desired.

For the last claim, assume that $\mu$ has no atoms and M is a perfect matching of $G_\omega$. Since $\mu (X_A)=\sum _{y\in Y}M(A, y)$, by [6, 215D] there exists a partition $\{X_{A,i}\}_{i=1}^{N}$ of each $X_A$ into N sets, satisfying $\mu (X_{A,i}) = M(A, y_i)$ for each $i\in \{1,\ldots , N\}$. Now define T by $T(x) := y_i$ for $x \in X_{A,i}$.

Recall that if $y_i \in A$, then $c(x, y_i) \le \omega$ for every $x \in X_A$. Since $\mu (X_{A,i}) = M(A, y_i) = 0$ if $y_i \not \in A$, we see that for $\mu$ almost every x, $c(x, T(x)) \le \omega$.

Also

$$\begin{aligned} \mu (T^{-1}(\{y_i\}))= & {} \mu \left( \bigcup _{A \in 2^Y} X_{A,i}\right) = \sum _{A \in 2^Y} \mu (X_{A,i})\\= & {} \sum _{A \in 2^Y} M(A, y_i)= w(y_i)= \nu (\{y_i\}) \end{aligned}$$

and so $({{\,\mathrm{Id}\,}}\times T)_\#\mu$ is a valid transport plan with cost at most $\omega$.$\square$

Remark 2.2

We remark that the proof of Theorem 1.5 actually gives a bijective correspondence between the collection of perfect matchings in $G_\omega$ and the collection of transport plans with cost at most $\omega$ modulo “rearrangement” inside of each cell $X_A$.

More rigorously: the construction gives a bijective correspondence between the collection of perfect matchings in $G_\omega$, and the collection of equivalence classes of transport plans with cost at most $\omega$, where each class consists of plans of the form given in (2.3) but the measures $\mu \big |_{X_A} \otimes \nu \big |_{\{y\}}$ can be replaced with any measures that share the same marginals.

Proof of Corollary 1.6

If a ${\mathcal {W}}_\infty$-optimal transport plan exists, the graph $G_\omega$ with $\omega ={\mathcal {W}}^c_\infty (\mu , \nu )$ contains a perfect matching by the first part of the above theorem, then we may apply the final statement in the theorem above to $G_\omega$.$\square$

3 Optimality bounds

In this section, we show that when the cost is a power of a p-norm, numerically solving the ${\mathcal {W}}_\infty$-optimal transport problem with a small error is at least as hard as the determining if a transport graph has a perfect matching. In particular, for the square Euclidean cost, we reduce the problem of finding a perfect matching in a transport graph to numerically solving the ${\mathcal {W}}_\infty$-optimal transport problem within an error of $\frac{1}{N}$. Indeed note that $\epsilon (N,2,2) = \frac{1}{N}$ in Proposition 3.3.

For this section, we will write $X_{A, \omega }$ for

$$\begin{aligned} X_{A, \omega } = \bigcap _{y\in A} \{x\in X\mid c(x,y) \le \omega \} \cap \bigcap _{y \not \in A} \{x\in X\mid c(x,y) > \omega \}. \end{aligned}$$

This is the same $X_A$ as in Definition 1.3, however we will be varying $\omega$ in this section and so we add it to our notation.

Proposition 3.1

Let $\Lambda \subset \mathbb {R}$ and c, X, Y be such that $\bigcap _{\omega \in \Lambda } X_{A, \omega } \ne \emptyset$ for every $A \subset Y$.

Then for every transport graph G, there exists a pair of probability measures $(\mu , \nu )$ so that $G=G_\omega$ for every $\omega \in \Lambda$ where $G_\omega$ is the transport graph defined using $(\mu , \nu )$ in Definition 1.3.

Proof

Fix a transport graph G with vertex weight function w. For each $A \subset Y$, choose a point $x_A \in \bigcap _{\omega \in \Lambda } X_{A, \omega }$, then define $\mu$ by $\mu = \sum _{A \subset Y} w(A) \delta _{x_A}$ and $\nu$ by $\nu = \sum _{y \in Y} w(y) \delta _{y}$. Since for each $\omega \in \Lambda$, $\{X_{A, \omega }\}_{A\in 2^Y}$ is a disjoint collection by Lemma 2.1 and we have $x_A \in X_{A, \omega }$, we see $\mu (X_{A, \omega }) = w(A)$ and so $G_\omega = G$.$\square$

Proposition 3.2

Suppose that G is a transport graph, $\Lambda \subset \mathbb {R}$, and $\mu \in {\mathcal {P}}(X)$, $\nu \in {\mathcal {P}}(Y)$ are measures such that $G_\omega = G$ for every $\omega \in \Lambda$. Then

• 1. $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \le \inf \Lambda$ if G has a perfect matching,

• 2. $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \ge \sup \Lambda$ if G does not have a perfect matching,

hence in all cases

$$\begin{aligned} \inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \in (-\infty , \inf \Lambda ]\cup [\sup \Lambda , \infty ). \end{aligned}$$

In particular, it suffices to solve (1.1) with this choice of $\mu$ and $\nu$ to an error of less than $\frac{{{\,\mathrm{diam}\,}}\Lambda }{2}$ in order to determine if G has a perfect matching.

Proof

Suppose that G has a perfect matching. Then for every $\omega \in \Lambda$, by Theorem 1.5, there exists a transport plan $\pi \in \Pi (\mu , \nu )$ so that $\Vert c \Vert _{L^\infty (\pi )} \le \omega$, hence $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \le \inf \Lambda$.

Now suppose that G does not have a perfect matching. Then for every $\omega \in \Lambda$, again by Theorem 1.5, there cannot exist any transport plan $\pi \in \Pi (\mu , \nu )$ with $\Vert c \Vert _{L^\infty (\pi )} \le \omega$, hence $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \ge \omega$. In particular, we obtain $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })} \ge \sup \Lambda$.

For the final claim, any interval of length $\epsilon < {{\,\mathrm{diam}\,}}\Lambda$ can only intersect one of $(-\infty , \inf \Lambda ]$ or $[\sup \Lambda , \infty )$. Thus determining $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })}$ within an error of $\epsilon$ will indicate which of the two cases above we are in, and hence if there is a perfect matching or not. $\square$

Proposition 3.3

Let $X = \mathbb {R}^N$, $y_i = e_i$ for $i \in \{1, \dots , N \}$, $q>0$, $p>1$, and $c = \Vert \cdot \Vert _p^q$. Then the hypotheses of Proposition 3.1 are satisfied with $\Lambda = (1 - \epsilon (N,p,q) ,1)$ where

$$\begin{aligned} \epsilon (N,p,q) :{=} 1 {-} \bigg ((1{-} (1{+}(N{-}1)^{\frac{1}{p{-}1}})^{{-}1})^p {+} (N{-}1)(1{+}(N{-}1)^{\frac{1}{p-1}})^{-p} \bigg )^{q/p} > 0. \end{aligned}$$

In other words, $\bigcap _{\omega \in (1 - \epsilon (N, p, q),1)} X_{A, \omega } \ne \emptyset$ for every $A \subset Y$.

Proof

Set $\alpha := (1+(N-1)^{\frac{1}{p-1}})^{-1}$ and for each $A\subset Y$, define $x_A \in \mathbb {R}^N$ by

$$\begin{aligned} x_A^i := {\left\{ \begin{array}{ll} \alpha &{}\quad \text { if } y_i \in A,\\ 0 &{}\quad \text { else.} \end{array}\right. } \end{aligned}$$

We claim that $x_A \in \bigcap _{\omega \in \Lambda } X_{A, \omega }$. First fix some $y_k=e_k \not \in A$. Then $\Vert x_A - y_k \Vert _p^q = (1 + \alpha ^p {\left| A\right| })^{q/p} \ge 1$ and so $c(x_A, y_k) \ge \omega$ for every $\omega \in (1 - \epsilon (N,p,q) ,1)$. Next fix some $y_k=e_k \in A$. We have

$$\begin{aligned}&\Vert x_A - y_k \Vert _p^q = \bigg ((1- \alpha )^p + \alpha ^p {(\left| A\right| -1)} \bigg )^{q/p}\\&\quad \le \bigg ((1- \alpha )^p + \alpha ^p {(N-1)} \bigg )^{q/p} = 1 - \epsilon (p,q,N) \end{aligned}$$

and so $c(x_A, y_k) \le \omega$ for every $\omega \in \Lambda$. This shows that $x_A \in \bigcap _{\omega \in \Lambda } X_{A, \omega }$ as desired.

We note that $\epsilon (N,p,q) > 0$ since $\alpha$ is the minimizer of the function $g(t) := (1- t)^p + t^p {(N-1)}$ over $t \in [0,1]$. Since $p>1$, it is not hard to see that $g'<0$ near 0, hence $g(t) < g(0)=1$ when $t < 1$ is very close to 0, thus we obtain $g(\alpha )^{q/p} < 1$. $\square$

4 Numerical examples

4.1 Description of the algorithm

The proposed algorithm is a bisection algorithm that estimates the value of the optimal $\infty$-transport cost, and then produces an approximation of the solution to the decision problem. Suppose that the optimal cost ${\mathcal {W}}^c_\infty (\mu , \nu )$ is known to lie in some interval $[\omega _1, \omega _2]$. We then query a decision algorithm in order to see if it is possible to produce a plan with cost less than $\frac{\omega _1 + \omega _2}{2}$, or in other words, whether ${\mathcal {W}}^c_\infty (\mu , \nu )$ lies in the upper or lower half of the interval $[\omega _1, \omega _2]$. We then divide the interval $[\omega _1, \omega _2]$ in half, and recursively continue the process until we reach a plan whose transport cost is within some specified error tolerance of the true value ${\mathcal {W}}^c_\infty (\mu , \nu )$. Note that if c is bounded (which we will assume for the remainder of the paper), we may always begin with the choice $[\omega _1, \omega _2]=[\min c, \max c]$.

Proposition 4.1

If G is a transport graph, it has a perfect matching if and only if for every $A \in L$, $\sum _{l\in A} w(l) \le \sum _{r \in \Gamma (A)} w(r)$ (recall Definition 1.1).

Proof

This is a version of Hall’s theorem and its proof is essentially the same as the first proof of [2, Section III.3, Theorem 7]. We interpret $\left| S\right|$ as the sum of the weights in S, use the version of the max-flow min-cut problem in [2, Section III.1, Theorem 4], and note that for a transport graph, Bollobás’ notion of complete matching implies perfect matching. $\square$

By Proposition 4.1 and Theorem 1.5, Algorithm 1 can be used as the decision algorithm in the binary search process mentioned above. Once we find $\omega$ that is sufficiently close to the optimal value $\inf _{\tilde{\pi }\in \Pi (\mu , \nu )} \Vert c \Vert _{L^\infty (\tilde{\pi })}$, we use the Edmonds-Karp algorithm to compute a maximal matching in $G_{\omega }$. Finally from this maximal matching, we obtain a transport plan via the method of the proof of Theorem 1.5.

We remark that Algorithm 1 terminates in $2^N$ steps and that when applied to $G_\omega$, the Edmonds-Karp algorithm terminates in at most $O(N4^N)$ steps, see [5, Theorem 26.8].

4.2 Numerical experiments

In all of the following numerical examples, the source measure $\mu$ is equal to the Lebesgue measure (normalized to the unit mass) restricted to the square $X=[0, 4]^2\subset \mathbb {R}^2$ and the cost function used is $c(x, y)=\Vert x-y\Vert _\infty$. The target will consist of a finite collection of points $Y=\{y_1, \ldots , y_N\}\subset X$ for some N. The code has been made publicly available.¹

Fig. 1

Transportation of mass: Example 4.2

Fig. 2

The cells $X_A$: Example 4.2

For each example below, Figs. 1, 3, and 5 are graphical representations of the measures $\mu _i:= \sum _{A\in 2^Y}\frac{\pi (X_A\times \{y_i\})}{\mu (X_A)\nu (\{y_i\})}\mu \big \vert _{X_A}$ for each point $y_i\in Y$, where $\pi \in {\mathcal {P}}(X\times Y)$ is the approximate optimal plan produced by the algorithm, the sets $X_A$ are defined as in (1.2), and the quantity $\frac{\pi (X_A\times \{y_i\})}{\mu (X_A)\nu (\{y_i\})}$ is interpreted as 0 if $\mu (X_A)=0$ (see also (2.2)). Effectively, $\mu _i$ is the distribution of mass that is sent to the location $y_i$ under the plan $\pi$.

Figures 2, 4, and 6 give the sets $X_A$ for each subset $A\in 2^Y$. Empty cells are displayed in Examples 4.2 and 4.3, but are excluded in Example 4.4 due to the large number of cells. In all three examples, the algorithm is run to an upper bound on the error of $\left| \Vert c \Vert _{L^\infty (\pi )}-{\mathcal {W}}^c_\infty (\mu , \nu )\right| <10^{-6},$ and all three examples terminate after 24 iterations of Algorithm 1 above.

Example 4.2

$y_1=(0, 0)$, $y_2=(0, 4)$, $y_3=(4, 0)$, $y_4=(2, 2)$, $\nu =0.25(\delta _{y_1}+\delta _{y_2}+\delta _{y_3}+\delta _{y_4})$

Example 4.3

The points $y_1,\ldots , y_4$ are taken the same as in Example 4.2,

$$\begin{aligned} \nu =(0.1)\delta _{y_1}+(0.2)\delta _{y_2}+(0.4)\delta _{y_3}+(0.3)\delta _{y_4} \end{aligned}$$

Fig. 3

Transportation of mass: Example 4.3

Fig. 4

The cells $X_A$: Example 4.3

Fig. 5

Transportation of mass: Example 4.4

Fig. 6

The cells $X_A$: Example 4.4

Example 4.4

$y_1=(0, 0)$, $y_2=(0, 4)$, $y_3=(4, 0)$, $y_4=(2, 2)$, $y_5=(1, 3)$, $y_6=(3, 3)$, $y_7=(3, 1)$.

$$\begin{aligned} \nu =(0.15)\delta _{y_1}+(0.1)\delta _{y_2}+(0.1)\delta _{y_3}+(0.05)\delta _{y_4}+(0.2)\delta _{y_5}+(0.2)\delta _{y_6}+(0.2)\delta _{y_7} \end{aligned}$$