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

\begin{align} &\min_{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?

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?