Question

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!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top