Question

Network flow issues come up in dealing with natural disasters and other crises, since major unexpected events often require the movement and evacuation of large numbers of people in a short amount of time. Consider the following scenario. Due to large-scale flooding in a region, paramedics have identified a set of n injured people distributed across the region who need to be rushed to hospitals. There are k hospitals in the region, and each of the n people needs to be brought to a hospital that is within a half-hour's driving time of their current location (so different people will have different options for hospitals, depending on where they are right now). At the same time, one doesn't want to overload any one of the hospitals by sending too many patients its way. The paramedics are in touch by cell phone, and they want to collectively work out whether they can choose a hospital for each of the injured people in such a way that the load on the hospitals is balanced: Each hospital receives at most [n/k] people. Give a polynomial-time algorithm that takes the given information about the people's locations and determines whether this is possible.

Answer 1

Answer:

Check the explanation

Explanation:

Algorithm for solving flood condition:

We suggest an algorithm to resolve the flood condition by creating a flow network graph.

Let us assume for every patient "p" there is a node "2" and for every hospital "h" there is a node "uh" and there is an edge ()T, uh) exist between patient "p" and hospital "h" with flow capacity of 1 iff patient "p" is reachable to hospital "h" within a half-hour.

Then source node "s" is made between all the patient-nodes by an edge with flow capacity of 1 and then the sink "t" is made by linking all the hospital nodes by an edge with capacity "[n/k]".

There is an approach to send patients to hospitals: when there is a source "s" to sink "t" flow of "n". We can send 1 flow-unit from source "s" to sink "t" along the paths (s, yp, uh, t) whenever a probable approach is available to send patients.

This approach of sending patients to hospitals doesn't break the capacity limitation of edges. Hence we can send patient "p" to hospital "h" with 1 flow- unit if edge(m uh) permits at least 1 flow- unit.

The running-time of this algorithm is found by finding the time needed to solve max-flow graph with nodes O(n+k) and edges O($n^{k}$) edges.