Some Older but Perhaps Useful Notes on Networks and Matchings

More than 20 years ago, I was a postdoc at the Institut für Ökonometrie und Operations Research at the University of Bonn, an Institute headed by Prof. Bernhard Korte (who now heads Bonn’s Research Institute for Discrete Mathematics).  It was a fantastic year.  Also visiting that year were people like Bill Cunningham, Bill Cook, Andras Sebo, and many others.  I learned a lot that year, and many aspects of what I learned showed up in my future research.  I was fortunate that I had a position at Carnegie Mellon but was allowed to delay the start by a year so I did not have to worry about job hunting during that time.

I loved living in Bonn.  Though I spoke no German at the beginning and very little by the end, I had a great time there, bicycling around and exploring the various areas of the town.  It helped that I met Ilona, who would go on to be my wife, so we could share those explorations (and she could handle all the German things).

During the year, I taught a Ph.D. seminar on networks and matchings.  In the course of the seminar, I put together some notes on the topic, amounting to about 80 pages of material.  I recently came across the files for those notes, and am very impressed with the younger me:  I seemed to have a lot of time available during that period.  The notes are in an interesting format.  All the results (which are mainly proofs of correctness or algorithmic analysis) are broken into digestible pieces.  So, rather than ask “What is the complexity of this algorithm”, the result is broken down into a number of steps, leading up to the result.  I was trying to recreate the thought process that went into the proofs in the hope that would make it easier for students to follow and emulate.  It seemed to inspire at least some students:  two students (Thomas and Helga, who I would see periodically in the following years) brought together my notes and presented me with a bound copy at the end of the course, a copy I still keep proudly on my shelves.

I am not sure the value of 20 year old notes.  Some basic algorithms haven’t changed in that time of course:  Dijkstra’s shortest path, Edmonds and Karp’s max flow algorithm, and so on.  Other approaches have been supplanted in the intervening time, and certainly books like Ahuja, Magnanti, and Orlin’s Network Flows covers more material and more depth.  But having found my notes, I would not like to see them lost again, so here they are in case anyone finds them useful.  The way the notes were designed to be used, students would get a version without the boxed answers and would try to work through the problems on their own.  If I find the tex source, I’ll see if I can add a student version:  this is the instructor’s version.

Notes on Network Flows and Matchings by Michael Trick

2 thoughts on “Some Older but Perhaps Useful Notes on Networks and Matchings”

  1. If the class notes are just half as good as the introducing story, they still must be mindblowing. [Maybe I should refresh my knowledge of the “birthday problem” and its mechanics – but these stories where various people I basically just know from book covers or “you must have heard of” introductions are so highly interconnected in real life, freak me out every time, all the time.]

Leave a Reply

Your email address will not be published. Required fields are marked *