This week the University of Waterloo celebrated Bill Cunningham’s 65th birthday with a conference in his honour. Bill’s work is on graph matchings and matroids, specifically exact optimization, algorithms, and polyhedral combinatorics. For example, he gave the first polynomial-time algorithm to compute the strength of a graph. He completed his thesis at Waterloo under the supervision of Jack Edmonds; he has been a professor in Waterloo’s Combinatorics and Optimization department for about twenty years, and worked previously at Johns Hopkins, Bonn, and at Carleton University.
Together with Bill Cook, Bill Pulleyblank and Lex “Bill” Schrijver, Bill authored the celebrated textbook Combinatorial Optimization. This book really attracted me to combinatorial optimization as a graduate student. A couple of times this week his book has been cited for its excellent Amazon reviews, including this unique one:
This book was thoroughly written by great-minded Masters. It is well-organized in their topics and presentation. However, the book details is unbalnced, some chapters are overwhelm the data, and some others are insufficient. By the way, I graded this book a Very Good one. Worth Reading !!
I certainly agree with the first two sentences and the last one!
There were three days of talks from visitors. Here are just a few highlights out of the many excellent talks:
- Bill Pulleyblank described three applications of integer programming to sports scheduling, including re-alignment of the divisions of the National Hockey League, which he modelled as a quadratic assignment problem.
- Bill Cook, who according to Pulleyblank “regularly solves TSP instances with 300 zillion cities on his iPhone while he’s talking,” gave a very compelling talk on the TSP (travelling salesman problem). There is a movie called “Travelling Salesman” coming out in a few days, where the protagonists find fast algorithms for TSP and therefore are able to break encryption, hack in to banks, et cetera. Bill Cook did really make a TSP app for iPhone, but as a disclaimer, the movie is not based on a true story. As an aside, I really recommend reading his TSP book, which has quite a lovely balance of mathematical details and storytelling.
- András Sebő described his joint work with Jens Vygen on graphic TSP. This is a very hot topic: a 1.5-approximation was known since the 1970s, and in the span of 13 months, four separate papers found approximation ratios of 1.4999999999, then 1.461, then 1.444, and now 1.4 by Sebő and Vygen. The new result uses some of the machinery of Mömke-Svensson (the 1.461) and most unexpectedly of all, matroids! I will have to read this paper in detail because it seemed to be a tour de force in terms of using many different tools, while still being very simple overall. You simply try to keep most of your ears (from an ear decomposition) long (e.g., having ≥5 edges). It also gives the best known results for unweighted s–t tours and connected T-joins.
- Jim Geelen gave a very nice new characterization of graphic matroids, joint with Bert Gerards; here is a nice alternate description that he gave of the result. You are given a tree, a distinct label like “5” for each edge, and some paths in the tree. Every path in the tree can be described by the set of labels it contains. Now I just write down the sets of labels corresponding to paths, but I erase the tree and its labels. Can you reconstruct a tree and paths giving these label sets? And, can you tell when I am cheating, giving you label sets that have no such realization? They show that this problem can be solved just by inspecting a certain system of linear equations. As a bonus, this gives a nice new solution for the consecutive ones property of hypergraphs: given a matrix with 0 and 1 entries, can you permute the columns so that in each row all the ones are consecutive?
- and, many other excellent talks on matroids, matchings, and extensions!
It has been a great week, thanks to the formidable organizers and the excellent speakers. Bill is extremely approachable, scientifically adept, and very dedicated: he served as Chair of the department several times. Here is a picture created by Bill Cook, based on a vintage photograph of Bill Cunningham. It shows a picture of a random Euclidean b-matching instance, solved to optimality. I believe that the value of b is “Bill.”
Happy birthday, Bill!
Filed under: combinatorial optimization, toc, waterloo | Leave a Comment