# Computing discrete optimal transport

I am trying to find a combinatorial approach to solve the following optimization problem.

\begin{align} &\max_{x_{ij}} C_{ij} x_{ij}, \\ &\text{such that},\\ &\sum_{j} x_{ij} \leq r_i~\forall i \in [N],\\ &\sum_{i} x_{ij} \leq c_j~\forall j \in [M],\\ &x_{ij} \geq 0~\forall i,j, \end{align} where the constants satisfy: $$C_{ij} \geq 0$$, $$\sum_i r_i = 1$$.

If $$\sum_j c_j = 1$$ then, I think, this problem is similar to the discrete (finite) optimal transport problem.

I am not interested in the most efficient solution approach. I am interested in an approach that reveals any interesting structure of a solution if such a structure exists.

In particular, is there a greedy algorithm (after sorting the weights $$C_{ij}$$) that solves this problem?

• Once you reformulated the problem such that you have a nontrivial minimiser, check out the assignment problem and the Hungarian algorithm.
– Dirk
Oct 25 '19 at 19:16
• Now with max instead of min, the answer is not so clear to me anymore. You may check standard literature on optimal transport (not necessarily discrete) for results that don't assume positivity of the cost function (there are quite of lot of them).
– Dirk
Oct 26 '19 at 8:35