Conference Scheduling with Graph Algorithms

Contents

Problem Statement

The Harvey Mudd Clinic Program has been a model for programs like it across the globe. In it, student teams are connected with corporate sponsors to define, design, and provide solutions to real world engineering problems.

Projects Day, at the end of every academic year, is when these teams and all of the corporate sponsors and friends of the HMC Community get together to celebrate Clinic and hear talks about each of the projects from that year.

Like most conferences, there is too much to see. Thankfully, each team gives their talk three times in the afternoon. The question is, how can we figure out when to go to which talk?

Preliminary Design

MATLAB can help us here. Let’s pick the 6 talks we want to go see:

  • 1:30, 2:00, & 4:00 – eSolar
  • 1:30, 2:30, & 3:30 – City of Hope
  • 2:00, 3:30, & 4:00 – HMC Online
  • 1:30, 2:00, & 4:30 – Lawrence Berkeley National Labs
  • 2:00, 2:30, & 4:00 – Walt Disney
  • 2:30, 3:00, & 4:00 – Sandia National Labs

We can make a matrix with topics as rows, times as columns, and ones where a talk is actually given at that time:

%	1:30	2:00	2:30	3:30	4:00	4:30
A = [ ...
	1	1	0	0	1	0 ; ... eSolar
	1	0	1	1	0	0 ; ... City of Hope
	0	1	0	1	1	0 ; ... HMC Online
	1	1	0	0	0	1 ; ... Lawrence Berkeley National Labs
	0	1	1	0	1	0 ; ... Walt Disney Animation Studios
	0	0	1	1	1	0]; ... Sandia National Labs

Now we know when we can go to all of the talks we want to go to. What we want, though, is to transform A into a matrix B that only has one entry in each row and column. This would be our selection. How can we do this in a way guaranteed to maximize the amount of talks we can attend while arbitrating conflicts?

Bipartite Graphs

Here, the matrices A and B that we are talking about are adjacency matrices: matrices that represent which elements of the two sets (rows and columns) are adjacent to one another (connected) in a graph. Because are rows and columns are distinct sets (in our case topics and times) the graphs we can describe are bipartite graphs: a graph on two sets where edges only connect one set to another. That is, there are no edges between topics and no edges between times. There are only edges connecting a topic to a time.

A is a bipartite graph of all of the talks that exist in the set of talks that we want to go see. B will be a subgraph of that, which connects at most each topic to one and only one time. It may be the case that there is an unresolveable conflict, in which case we will only be able to go to, say, 4 or 5 of the 6 talks we want to go to. hopeful that won’t happen.

The Dulmage-Mendelsohn Decomposition

There are many algorithms out there that feel like they are magic, and this is one of them.

The Dulmage-Mendelsohn Decomposition (or permutation) is briefly documented in MATLAB’s dmperm, and more thoroughly described (and defined) in the 1958 classic “Coverings of Bipartite Graphs” by A. L. Dulmage and N. S. Mendelsohn.

I love the details and genius in the paper, which can be a little exhausting, but the idea is that all bipartite graphs, full of edges or only with very few edges, may be made of strongly connected, connected, and/or disconnected components with respect to one of the sets. We should be able to traverse the graph in a particular way to determine which edges are in which category, and then to label them in some way for further analysis. dmperm does just that:

[p,q] = dmperm(A)

p =

     4     1     3     2     6     5

q =

     6     1     2     3     4     5

Here, p and q tell use how to reorder the rows and columns to give us, visually, the block structure of these components. In our case, we have a single, well-determined component (the other outputs of dmperm tell us this). Further, that component gets organized into the strongly connected components.

Looking at the permuted matrix:

A(p,q)

ans =

     1     1     1     0     0     0
     0     1     1     0     0     1
     0     0     1     0     1     1
     0     1     0     1     1     0
     0     0     0     1     1     1
     0     0     1     1     0     1

we see the block upper-triangular form that A has been put into. In this case, however, we only have two blocks of sizes 1×1 and 5×5 along the diagonals. Most notably for our application, we see that there are ones in every diagonal element. This means that we can go to every talk we wanted! Can you see why?

Making our Schedule

Let’s prepare our B matrix by filling it with zeros. If we then index into B using our permutation vectors from dmperm, we can tell the permutation of B to be the 6×6 identity matrix (one and only one topic per time for all times). In B, then, will be in the inverse permutation of the 6×6 identity matrix, telling us with respect to our original talk and time ordering when we should be where!

B = zeros(6);
B(p,q) = eye(6)

B =

     1     0     0     0     0     0
     0     0     1     0     0     0
     0     1     0     0     0     0
     0     0     0     0     0     1
     0     0     0     0     1     0
     0     0     0     1     0     0

Another way to think about the permutations of rows and columns is just to look at the sets of graph

topics = {'eSolar';'City of Hope';'HMC Online';'LBNL';'Disney';'SNL'};
times = {'1:30';'2:00';'2:30';'3:30';'4:00';'4:30'};
sortrows([times(q) topics(p)])

ans = 

    '1:30'    'eSolar'
    '2:00'    'HMC Online'
    '2:30'    'City of Hope'
    '3:30'    'SNL'
    '4:00'    'Disney'
    '4:30'    'LBNL'        

to get our schedule. Can you see how this matches up with our matrix B?

References

Advertisements

One Response to “Conference Scheduling with Graph Algorithms”

  1. Losing Weight with … Graph Algorithms!? | that's gross Says:

    […] my "preemptive" "strike" on "content" « Conference Scheduling with Graph Algorithms […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: