Graph problem for algorithm geeks

Input: Undirected bipartite graph G = (V,E); V = V1 union V2; V1 and V2 disjoint; E subset of {(vi, vj) | vi in V1, vj in V2}

Output: Undirected bipartite graph H = (V,F); F subset of E such that at most s edges in F contain vi in V1 and exactly one edge in F contains vj in V2.

In English:
I'm writing a program for my wife to help her schedule panelists at her lab. Panelists indicate the time slots they are able to work, and it's up to the program to put each panelist in exactly one time slot according to their available while not putting more than 8 panelists in the same time slot.

I have already implemented an algorithm that enumerates all possible panelist/slot pairs based on panelist availability and checks to make sure the slots are not over-filled, but this is worst case O(m^n) where m is the number of slots and n is the number of panelists. This works fine for some cases, but explodes for others, so I need a solution with some intelligence.

Do any of you have any suggestions? I'm going to look at known problems to see if I can throw it into NP or find a solution, but since I know some of you have degrees in computer science, computer engineering, and mathematics, I figured I'd check here first.

I found the generalized assignment problem. I can translate time slots to bins and panelists to items, fix the profits to 1 and item weights to either 1 or infinity depending on if the item (panelist) is allowed to fit in (work during) the bin (time slot), and set the max weights to 8. Running the approximation algorithm should work.

Do the panelists have to be as evenly distributed on time slots as possible? For example avoid giving one time slot 6 panelists, and leaving 5 time slots without any?

Do all panelists need to work (i.e. does each panelist need his/her time slot?) That means that the original graph needs each vertex of V2 to be connected.

printz said:

Do the panelists have to be as evenly distributed on time slots as possible? For example avoid giving one time slot 6 panelists, and leaving 5 time slots without any?

No.

Do all panelists need to work (i.e. does each panelist need his/her time slot?) That means that the original graph needs each vertex of V2 to be connected.

Yes.

EDIT: The solution I described in my second post seems to work. The program is now lightning fast and appears to produce correct results.

I scanned each edge and deleted those for which one of their vertices had a higher degree than allowed. I don't know if repeated scanning was necessary.

printz said:

I scanned each edge and deleted those for which one of their vertices had a higher degree than allowed. I don't know if repeated scanning was necessary.

Hmmm, I'll have to think about that.

See if it doesn't err; I only tried that on two cases so far.

You could potentially cut off a panelist from all of his/her time slots if all of his/her slots are over-filled and you scan his/her edges first.

Unless I'm missing something, this should reduce to the ordinary assignment problem if you replace each "time slot" vertex with 8 identical vertices (same adjacencies to the panelists) and then seek an assignment saturating the panelists. Any bipartite matching algorithm (e.g., Hopcroft-Karp) should be able to handle that in time polynomial in s*n.

(Not that it matters anymore since you already solved the actual problem...)

Gebstadter said:

Unless I'm missing something, this should reduce to the ordinary assignment problem if you replace each "time slot" vertex with 8 identical vertices (same adjacencies to the panelists) and then seek an assignment saturating the panelists. Any bipartite matching algorithm (e.g., Hopcroft-Karp) should be able to handle that in time polynomial in s*n.

(Not that it matters anymore since you already solved the actual problem...)

Thanks. That does indeed seem like a better way to approach the problem. The implementation I settled on is a lot cleaner than that Hopcroft-Karp pseudocode, though, so unless I see any more performance issues, it's unlikely that I'll change anything.

EDIT: I thought about this as I was falling asleep last night, and I changed my mind. I'm going to use Hopcroft-Karp because my current greedy approximation can leave panelists unscheduled, and I want my code to be as awesome as possible. Thanks again for pointing out this solution. I wasn't exposed to many graph problems or algorithms during my undergraduate education in computer engineering even though I minored in math and CS and took an upper-division algorithms class.

I may as well put this here in case any of you are interested in what I came up with. It's pretty rough, but it does the job.

https://github.com/delbel/panelsched/blob/master/panelsched.c

exp(x) said:

You could potentially cut off a panelist from all of his/her time slots if all of his/her slots are over-filled and you scan his/her edges first.

I wonder if that can be fixed if I add a restriction of minimum degree (don't delete those edges with vertices of minimum degree — in this case a panelist with one last time slot remaining). I wonder if it's a puzzle of choosing the correct sticks (edges) to remove, or if the choice can be arbitrary until the conditions are met.

Gebstadter's interpretation of the problem is correct, so you may want to look there for answers if you're curious. Now that I found an optimal complete solution, I'm no longer interested in alternatives :)

Quick question for geometry geeks:
How much more surface area would Earth have if it were 1cm wider in diameter?

Bucket said:

Quick question for geometry geeks:
How much more surface area would Earth have if it were 1cm wider in diameter?

Assuming the Earth is a perfect sphere of exact radius 6,371km (which it obviously is not):

4*pi*(6,371*10^3 + 0.5*10^-2)^2 - 4*pi*(6,371*10^3)^2

About 0.08km^2