0
$\begingroup$

I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such:

Assume there are x restaurants, each with a capacity q, and y people, each of which can only eat from one restaurant. The x restaurants can only serve the people within radius r of its location. Try and find the maximum number of people that can be served by a restaurant and what restaurant each one must eat from.

My approach was to split it up into something similar to the bipartite matching problem. Have the x restaurants on one side and y people on the other. Then, I'd have a start node which connects to every restaurant using a directed edge of capacity q. Then, I'd connect all the y people with a directed edge of capacity 1 to a sink node, t. Lastly, I'd connect every restaurants to all the people within radius r using a directed edge of capacity 1.

Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could (for example, let's say we have two restaurants each with capacity 2, 4 people, and the first restaurant connects to the first three people and the second connects to the last two; then, if the path from the first restaurant to the third is augmented in the algorithm, we can only serve 3 people instead of an optimum of 4). My workaround to this is maybe augment an s-t path with the least amount of incoming edges to the person (so a situation like the above can be avoided), but this clearly slows down the efficiency significantly of the algorithm, as well as making it much more difficult to provide an argument saying it's optimal.

Is there any literature concerning problems like these, or any suggestions on how I can improve my approach? Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ "Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could" - Double-check your reasoning. That statement looks wrong. I didn't understand your example. Anyway, the maximum flow is 4, and Ford-Fulkerson will indeed find that maximum flow. Try executing F-F by hand on the example, and if you still don't see how it gets the maximum flow, edit your question to show the sequence of states that the graph goes through in each step (use pictures). I suspect you might just be misunderstanding how F-F works. $\endgroup$
    – D.W. ♦
    Commented Apr 10, 2016 at 0:37
  • $\begingroup$ The problem that I provided was supposed to look something like this: (ignore the crappy quality) imgur.com/NaLHXmc. Could the end result not be this, where only 3 people are served: imgur.com/qXJcrJk? $\endgroup$
    – podington
    Commented Apr 10, 2016 at 3:47
  • $\begingroup$ No. That can't be the final stage of F-F, because there's an augmenting path from the source to the sink in your residual graph. It's hard to explain in words, without a picture, but starting from the source, go down (to the 2nd restaurant), then right (to the 3rd person), then up-and-left (to the 1st restaurant), then right (to the 1st person), then right (to the sink). As I suspected: you haven't quite understood Ford-Fulkerson yet. $\endgroup$
    – D.W. ♦
    Commented Apr 10, 2016 at 3:59
  • $\begingroup$ Oh, wow, I didn't see the edge going back to the restaurant and to the first person before. Thanks! $\endgroup$
    – podington
    Commented Apr 10, 2016 at 4:43

1 Answer 1

Reset to default
1
$\begingroup$

Your approach works. The situation you're worried about can't happen. It appears you haven't quite fully grasped how the Ford-Fulkerson algorithms yet, so focus on getting more familiar with it. It always finds the max-flow, and the max-flow always solves your problem.

The key misunderstanding is where you wrote:

Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could

This is false. That actually can't happen. Work through the proof of correctness for the Ford-Fulkerson algorithm to understand why not: if there's a larger flow, then there will always be an augmenting path you can find to increase the size of the flow.

This was presumably an exercise to help you get acquainted with network flow algorithms, and it worked: it uncovered a gap in your understanding. This is great -- it means you have something yet to learn about how the algorithms work. What a great opportunity! Now you get to spend some time communing with a textbook learning this lovely subject. Have fun!

Improve this answer
$\endgroup$
0

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.