4
$\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$
  • 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$ – Seb Destercke Jan 10 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$ – narek Bojikian Jan 10 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$ – narek Bojikian Jan 10 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$ – Yuval Filmus Jan 10 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$ – Yuval Filmus Jan 10 at 11:23
5
$\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$
  • 1
    $\begingroup$ What kind of train of thought was it that identified network flows a plausible solution? $\endgroup$ – Sudix Jan 11 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. Jan 11 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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