I was told this question would be better suited here:

Suppose you have a table such as:

$\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|& 27\\ 1.019 & 2.045 & 0.936 &|& 4\\ 26&22&7&|&55 \end{array}$

Where the rows add up to the numbers on the right and the columns add up to the numbers on the bottom. How can we determine whether there is a valid arrangement of each number using ceiling and floor so that the sum of the rows and columns stays the same? For example, this has a valid arrangement because we can do:

$\begin{array}{ccc} 11 &10 & 3 &|& 24\\ 13 & 10 & 4 &|& 27\\ 2& 2 & 0 &|& 4\\ 26&22&7&|&55 \end{array}$

I'm supposed to use a network flow computation to solve the problem, but I can't figure out a way to arrange the nodes and edges so that I end up "discovering" whether the flow is valid. Do I have to create multiple graphs that each compute a separate flow (e.g. one for each column and one for each row)? I'm guessing that we have to end up with saturated edges at the end of our flow graph, but I'm not sure how to specify the graph so it solves the problem.


You want to translate this into a graph problem (specifically, a network flow problem).

Hint: graphs often arise when you have relationships between two entities. Then each entity becomes a vertex, and each relationship becomes an edge. Do you see anything like that here?

  • $\begingroup$ Thank you for the response. I think I understand how to formulate the graph to solve the problem using Ford-Fulkerson, but I'm having a hard time proving that an arrangement of floors and ceilings will always solve the problem. In particular, how can we prove that if we take the floor and ceiling of every number, a solution will always exist? $\endgroup$ – Jenn Parker Oct 20 '14 at 5:59
  • $\begingroup$ @JennParker, that's a different question. It's important to ask the question that you want an answer to. I answered the question as it currently appears -- it asks for "a way to arrange the nodes and edges". "Chameleon questions" (where when you answer the question that was asked, the question changes) are not much fun to answer, and not the best way to solve your problem. I suggest you edit your question... and make sure to show what you've tried and where you got stuck. $\endgroup$ – D.W. Oct 20 '14 at 6:08

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.