During the pandemic, traveling nurses must be sent to places where infection rates are spiking. There...

 

Transcribed Image Text:

During the pandemic, traveling nurses must be sent to places where infection rates are spiking. There are P different nurse practitioners, denoted by Pi, and there are H different hospitals that they can be assigned to. Obviously, each nurse can be assigned to at most one hospital. Each hospital h; has a demand for d; nurse practitioners. However, not every nurse is eligible to work at every hospital; for each nurse practitioner p; we are given the set s; of hospitals at which they are approved to work. Find an algorithm to decide whether there is a way to meet the demand for nurse practitioners at every hospital. 1. Design the graph G that is an instance of the max-Flow problem and corresponds to the Traveling Nurses problem. Describe each part of G in such detail that another person would be able to draw G based on your description. (It is fine to include a picture, but you still have to explain what we see.) 2. How many vertices does your graph have in terms of P and H? (State the exact number, no proof needed.) 3. How many edges (exactly) does your graph have (as a function of the input parameters) and why? (A one-two sentence explanation is sufficient.) 4. Suppose we found the maximum flow f in G. Explain how to find for each nurse practitioner Pi which hospital they are sent to based on the flow values f(e) along the edges. Explain briefly why with your graph design we know that each nurse is assigned to at most one hospital. 5. How much does the value of the maximum flow need to be at least so that all demand can be met? During the pandemic, traveling nurses must be sent to places where infection rates are spiking. There are P different nurse practitioners, denoted by Pi, and there are H different hospitals that they can be assigned to. Obviously, each nurse can be assigned to at most one hospital. Each hospital h; has a demand for d; nurse practitioners. However, not every nurse is eligible to work at every hospital; for each nurse practitioner p; we are given the set s; of hospitals at which they are approved to work. Find an algorithm to decide whether there is a way to meet the demand for nurse practitioners at every hospital. 1. Design the graph G that is an instance of the max-Flow problem and corresponds to the Traveling Nurses problem. Describe each part of G in such detail that another person would be able to draw G based on your description. (It is fine to include a picture, but you still have to explain what we see.) 2. How many vertices does your graph have in terms of P and H? (State the exact number, no proof needed.) 3. How many edges (exactly) does your graph have (as a function of the input parameters) and why? (A one-two sentence explanation is sufficient.) 4. Suppose we found the maximum flow f in G. Explain how to find for each nurse practitioner Pi which hospital they are sent to based on the flow values f(e) along the edges. Explain briefly why with your graph design we know that each nurse is assigned to at most one hospital. 5. How much does the value of the maximum flow need to be at least so that all demand can be met?