1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Network Flow - Bipartite Matching

  1. Nov 8, 2016 #1
    1. The problem statement, all variables and given/known data
    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).
    3. 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?
     
  2. jcsd
  3. Nov 13, 2016 #2
    Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.
     
  4. Nov 26, 2016 #3
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Network Flow - Bipartite Matching
  1. Impedance matching (Replies: 3)

  2. Neural Network (Replies: 1)

Loading...