# Network Flow - Bipartite Matching: Doctors Without Weekends Problem

Problem

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.

1. 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).
2. 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_i$ doctors 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).

My Thoughts

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. 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?

• Yes, if $p_i > k$ on any link to the sink then a schedule can never be found. I don't see the problem... Sometimes (like in that situation), no schedule can be found -- and in such cases, your program should simply say so. If a schedule can be found, your program should describe one of them. No-one is asking you to report a schedule when one doesn't exist! – j_random_hacker Nov 9 '16 at 13:24
• Turns out the question is not worded well. (My take from the professor's comments.) There are suppose to be gadget nodes to enforce the constraint with C... I opted to perform the same task in code differently. – Nolan Robidoux Nov 19 '16 at 9:42