CS 330, Spring 2021, Homework 9
Algorithm代做 – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 涵盖了Algorithm等方面
Due Monday, April 26, 2021
Problem 1 Traveling Nurses
During the pandemic, traveling nurses must be sent to places where infection rates are spiking. There arePdifferent nurse practitioners, denoted bypi, and there areHdifferent hospitals that they can be assigned to. Obviously, each nurse can be assigned to at most one hospital. Each hospitalhjhas a demand fordjnurse practitioners. However, not every nurse is eligible to work at every hospital; for each nurse practitionerpiwe are given the setsiof 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.
- (2 pts.) Design the graphGthat is an instance of the max-Flow problem and corresponds to the Traveling Nurses problem. Describe each part ofGin such detail that another person would be able to drawGbased on your description. (It is fine to include a picture, but you still have to explain what we see.)
- (1 pts.) How many vertices does your graph have in terms ofPandH? (State theexact number, no proof needed.)
- (1 pts.) How many edges (exactly) does your graph have (as a function of the input param- eters) and why? (A one-sentence explanation is sufficient.)
- (1 pts.) Suppose we found the maximum flowf inG. Explain how to find for each nurse practitionerpiwhich hospital they are sent to based on the flow valuesf(e) along the edges.
- (2 pts.) Suppose that it is indeed possible to assign nurses so that all demands are met. In that case, what is a lower bound onval(f) for the flow that is returned by the max-flow subroutine? Show a minimum st-cut in this graph. (Please write out the nodes in the set of the cut thatsis in, dont just draw a picture with a line.) Is it possible that the value of the maximum flow is in fact larger than the lower bound you just gave? Prove your answer.
Problem 2 Decreasing the maximum flow.
LetG(V, E, s, t, c) be a directed graph, with designated sources, sinktand anintegercapacity c(e) on each edge. Suppose we are given the maximum flowfonG. Remember,f is a function that can be specified by giving the exact valuef(e) for each edgee.Further, we are given an integerk.
Our goal is to reduce the value of the maximum flow by at mostkby reducing the capacity along some of the edges inE. (Note, that if the maximum flow is less thank, then we cannot reduce by more than the value of the max flow.)
- (5 pts.) Design an algorithm that specifies the set of edges and their new (decreased) capacities to achieve our goal. Your algorithm doesnot need to find the updated flow along the edges, only the decreased capacities. (There may be multiple solutions to reduce capacities. Your algorithm only has to find one of them, it doesnt matter which one.)
- (1 pt. ) Analyze the running time of your algorithm.
- ( 2 pts. ) Prove that your algorithm is correct.