5
$\begingroup$

Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an efficient algorithm that will determine if there's a matrix $B_{n\times n} = \{b_{ij}\}$ , $b_{ij} \in \mathbb{Z}$ and

for every $1\leq i \leq n \sum b_{ij} = r_i$

for every $1\leq j \leq n \sum b_{ij} = c_j$

and

$0 \leq b_{ij} \leq a_{ij}$

Thought something with dynamic programming but didn't manage to solve it.

$\endgroup$
9
  • 2
    $\begingroup$ $b_{ij} \leq a_{ij}$ is where they are used. Since your constraints are all linear, do you mean an algorithm more efficient than linear programming? $\endgroup$ Commented Jan 10, 2020 at 6:53
  • 2
    $\begingroup$ Linear programming does not help a lot here since you are looking for integers. Unless you can prove that the polytope of this problem is integral.. $\endgroup$ Commented Jan 10, 2020 at 6:56
  • 1
    $\begingroup$ However, total unimodularity of the constraint matrix can be doable. I did not say it is not the case. Write down the LP formulation and look-up the proof of unimodularity of the incidence matrix of bipartite graphs. This should be a similar proof (if it was unimodular) $\endgroup$ Commented Jan 10, 2020 at 7:08
  • 3
    $\begingroup$ Such matrices are known as contingency tables, and even when $a_{ij} = \infty$, counting them is #P-hard, even for only two rows! $\endgroup$ Commented Jan 10, 2020 at 10:53
  • 1
    $\begingroup$ @narekBojikian Same issue as with perfect matchings (which is a special case). Counting is hard, determining if any exists is easy. $\endgroup$ Commented Jan 10, 2020 at 11:23

1 Answer 1

7
$\begingroup$

Hint #1:

This can be solved with network flow.

Hint #2:

Imagine $r_i$ units of flow entering the $i$th row, and $c_j$ units of flow leaving the $j$th column. Does that give you any hints how to set up the graph for a network flow problem?

$\endgroup$
2
  • 1
    $\begingroup$ What kind of train of thought was it that identified network flows a plausible solution? $\endgroup$
    – Sudix
    Commented Jan 11, 2020 at 9:09
  • 1
    $\begingroup$ @Sudix, for me, I think that I tried to solve it for the special case of 0-or-1 instead of arbitrary integers; and I think I noticed that there was summing of variables and upper/lower bounds on the variables and the variables were integers, which reminded me of network flow. In retrospect, a more direct path to it would have been the comments about linear programming and total unimodularity: network flow is a special case of linear programming where total unimodularity holds. $\endgroup$
    – D.W.
    Commented Jan 11, 2020 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.