{"id":1266,"date":"2010-11-12T14:57:29","date_gmt":"2010-11-12T18:57:29","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1266"},"modified":"2010-11-12T14:57:29","modified_gmt":"2010-11-12T18:57:29","slug":"some-older-but-perhaps-useful-notes-on-networks-and-matchings","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/11\/12\/some-older-but-perhaps-useful-notes-on-networks-and-matchings\/","title":{"rendered":"Some Older but Perhaps Useful Notes on Networks and Matchings"},"content":{"rendered":"

More than 20 years ago, I was a postdoc at the Institut f\u00fcr \u00d6konometrie und Operations Research at the University of Bonn, an Institute headed by Prof. Bernhard Korte<\/a> (who now heads Bonn’s Research Institute for Discrete Mathematics<\/a>).\u00a0 It was a fantastic year.\u00a0 Also visiting that year were people like Bill Cunningham<\/a>, Bill Cook<\/a>, Andras Sebo<\/a>, and many others.\u00a0 I learned a lot that year, and many aspects of what I learned showed up in my future research.\u00a0 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.<\/p>\n

I loved living in Bonn.\u00a0 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.\u00a0 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).<\/p>\n

During the year, I taught a Ph.D. seminar on networks and matchings.\u00a0 In the course of the seminar, I put together some notes on the topic, amounting to about 80 pages of material.\u00a0 I recently came across the files for those notes, and am very impressed with the younger me:\u00a0 I seemed to have a lot of time available during that period.\u00a0 The notes are in an interesting format.\u00a0 All the results (which are mainly proofs of correctness or algorithmic analysis) are broken into digestible pieces.\u00a0 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.\u00a0 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.\u00a0 It seemed to inspire at least some students:\u00a0 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.<\/p>\n

I am not sure the value of 20 year old notes.\u00a0 Some basic algorithms haven’t changed in that time of course:\u00a0 Dijkstra’s shortest path, Edmonds and Karp’s max flow algorithm, and so on.\u00a0 Other approaches have been supplanted in the intervening time, and certainly books like Ahuja, Magnanti, and Orlin’s Network Flows<\/a> <\/em>covers more material and more depth.\u00a0 But having found my notes, I would not like to see them lost again, so here they are in case anyone finds them useful.\u00a0 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.\u00a0 If I find the tex source, I’ll see if I can add a student version:\u00a0 this is the instructor’s version.<\/p>\n

Notes on Network Flows and Matchings by Michael Trick<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

More than 20 years ago, I was a postdoc at the Institut f\u00fcr \u00d6konometrie 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).\u00a0 It was a fantastic year.\u00a0 Also visiting that year were people like Bill Cunningham, Bill Cook, Andras … Continue reading “Some Older but Perhaps Useful Notes on Networks and Matchings”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[],"class_list":["post-1266","post","type-post","status-publish","format-standard","hentry","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1266"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1266\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}