Network Flow - Bipartite Matching

[nrobidoux]

Homework Statement

You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n days, the hospital has determined the number of doctors they want on hand; thus, on day i, they have a requirement that exactly p_i doctors be present.

There are k doctors, and each is asked to provide a list of days on which he or she is willing to work. Thus doctor j provides a set L_j of days on which he or she is willing to work.

The system produced by the consulting firm should take these lists and try to return to each doctor j a list L_j' with the following properties:

(A) L_j' is a subset of L_j , so that doctor j only works on days he or she finds acceptable.

(B) If we consider the whole set of lists L_1' ... L_k', it causes exactly p_i doctors to be present on day i, for i = 1, 2 ...n. (a) Describe a polynomial-time algorithm that implements this system.

Specifically, give a polynomial-time algorithm that takes the numbers p_1, ... p_n, and the lists L_1 ... L_k, and does one of the following two things.

• Return lists L_1' ... L_k', satisfying properties (A) and (B); or
• Report (correctly) that there is no set of lists L_1' ... L_k' that satisfies both properties (A) and (B).

(b) The hospital finds that the doctors tend to submit lists that are much too restrictive, and so it often happens that the system reports (correctly, but unfortunately) that no acceptable set of lists L_1' ... L_k' exists.

Thus the hospital relaxes the requirements as follows. They add a new parameter c > 0, and the system now should try to return to each doctor j a list L_j' with the following properties.

(A*) L_j' contains at most c days that do not appear on the list L_j.

(B) (Same as before) If we consider the whole set of lists L_1' ... L_k', it causes exactly p_idoctors to be present on day i, for i = 1, 2 ... n.

Describe a polynomial-time algorithm that implements this revised system. It should take the numbers p_1 ... p_n the lists L_1 ... L_k, and the parameter c > 0, and do one of the following two things.

• Return lists L_1' ... L_k' satisfying properties (A*) and (B); or
• Report (correctly) that there is no set of lists L_1' ... L_k' satisfies both properties (A*) and (B).

The Attempt at a Solution

Thank you for any guidance. This is an online class and unfortunately by the time I begin this there is little opportunity for teacher/student interaction... and I only post after looking on Google.

I appears to be a pretty straight forward bipartite matching network flow problem. My issue really arises from in either case that a schedule cannot be found.

To setup the graph place an edge from the source to each doctor with a flow [capacity] of 0[n]. This indicates that each doctor can participate in the Doctors W/O Weekends Program up to all the n days scheduling is needed for.

Adjacent to this setup will be all days in another column connected to the sink, with flow [capacity] of 0 [p_i].

The edges from doctors to days are spelled out in the respective set of available days submitted by each doctor (L_j). All are set to 0 [1].

Once max flow / Ford-Fulkerson (or whatever name the algorithm goes by) is run we will have a potential schedule.

Difficulty

For me it seems that the optimal schedule can be achieved... sometimes. Just not all the time, for both cases. I'm struggling to determine how neither case is correct... to say there is "no set of lists"...

The mathematical definition of a subset seems to indicate any set where all elements are contained within another set is a subset. It did not say the size had to be smaller (i.e. set A == B).

The only thing I can see is that the problem does not state p_i <= k is a requirement.

If p_i > k on any link to the sink then a schedule can never be found.

Is there something else I'm missing? I mean c can be set to n... at that point the only reason a schedule can't be found is because p_i > k. ... ... ... Right?

 

[nrobidoux]

Thanks Greg. Apparently the problem was the wording in the original problem. I received full credit for my answer... well almost. Apparently I needed some widget nodes in my graph and not handle c with any other code besides max-flow used on that graph.