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.

Improve this question
$\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$
    – Seb Destercke
    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$
    – Narek Bojikian
    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$
    – Narek Bojikian
    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$
    – Yuval Filmus
    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$
    – Yuval Filmus
    Jan 10, 2020 at 11:23

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ What kind of train of thought was it that identified network flows a plausible solution? $\endgroup$
    – Sudix
    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. ♦
    Jan 11, 2020 at 17:11

Your Answer

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

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