Semidiscrete Optimal Transport

Semidiscrete optimal transport refers to situations in optimal transport where two input measures are considered, and one measure is a discrete measure and the other one is continuous. Hence, because only one of the two measures is discrete, we arrive at the appropriate name "semidiscrete."

Formulation of the Semidiscrete Dual Problem

In particular, we will examine semidiscrete optimal transport in the case of the dual problem. The general dual problem for continuous measures can be stated as

$$\max {\Big \{}\int _{X}\varphi d\mu +\int _{Y}\psi d\nu :\varphi (x)+\psi (y)\leq c(x,y){\Big \}}$$

where $\mu ,\nu$ denote probability measures on domains $X,Y$ respectively, and $c(x,y)$ is a cost function defined over $X\times Y$. Now, we would like to extend this notion of the dual problem to the semidiscrete continuous, i.e., one of the two measures is discrete. Such a case can be reformulated as

$$\max {\Big \{}\int _{X}\varphi ^{c}d\mu +\sum _{j}\varphi _{j}b_{j}{\Big \}}$$