aviral0807's blog

Best time to fill a nxn matrix whose sum of each row and column is given.
By aviral0807, history, 4 years ago, In English

I was looking for a solution to the problem to fill an nxn matrix with positive integers. Given positive integers r1, r2, ..., rn, c1, c2, ..., cn.

Where ri is the sum of the ith row and cj is the sum of the jth column.

My thoughts suggest it is somewhat similar to the sudoku problem. Still not sure as the constraints are different.

Can anyone suggest an optimal way to do so? Any heuristic algorithm to solve it is also welcomed.

Thanks.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

Sounds like flow, depending on bounds.

4 layers: Source -> nodes representing rows -> nodes representing columns -> sink.

Edge from source to row node i has capacity r_i.

Edge from col node j to sink has capacity c_j.

Add an edge from every row node to every col node with capacity infinity.

Run your favorite max flow algorithm.

The flow on the edge from row node i to col node j gives us the value in the matrix of element a_ij.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

After knowing that this class of problem can be modeled by using max flow. I'm curious if a problem like this can also be modeled in such a manner?

There are three nxn matrices A, B, C. We have to fill the matrix A such that the row sum of matrix [Aij Bij] = ri, and column sum of matrix [Aij Cij] = cj. Here we are performing element-wise multiplication of AB and AC respectively.

Edit: Matrices B and C are already given to us.

→ Reply