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.
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).
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).
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 .
Once max flow / Ford-Fulkerson (or whatever name the algorithm goes by) is run we will have a potential schedule.
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?