Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:

$$
\begin{matrix}
&
\begin{bmatrix}
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0
\end{bmatrix}
&
\begin{pmatrix}
2\\2\\2
\end{pmatrix} = R
\\
C = &\begin{pmatrix}
3 & 3 & 0 & 0
\end{pmatrix}
\end{matrix}
$$

However, the row sum vector $R' = (4, 1, 1)$ doesn't form a match with $C$.

So given two vectors whose values are sorted in a non-increasing order $C_w$ and $R_h$, and whose accumulated sum is the same, $T = \sum_jc_j = \sum_ir_i$, how can I polynomically check if $C$ and $R$ form a matching because I can form a matrix $M_{h,w}$ having $C$ and $R$ as colum and row sum vectors respectively?

More specifically, in case it can help to make the check algorithm faster, in my specific case, C and R has the following properties:

• $h \leq w$

• The number of positive values of $R$ and $C$ is $> w$. For example, $C$, in the example, has two positive values and $R$ has three positive values, and it happens that $2 + 3 > w = 4$.

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem:

While the proof of theorem (1.1.13) is somewhat involved, the reconstruction algorithm that comes out of it is actually quite easy. It proceeds one column at a time, starting with a column whose sum is the highest and working in order down to the lowest column sum. In each column, we place the 1’s in those rows where with the largest number of 1-positions left, that is, such that the row sum minus the number of 1’s already filled in is the largest.

StackExchange Computer Science Q#130190, answer score: 6