Archive for the ‘combinatorial optimization’ Category

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 […]


Last week I was at an excellent summer school organized by TU Berlin and held at a nearby cottage/hotel. One topic that came up in a couple of talks was new to me: parametric search. First I’ll describe the setting and the basic result, due to Megiddo from 1979. In an optimization problem, we are […]


One well-known problem in mathematics is to determine the minimum number of colours that map-makers can use to draw a map such that adjacent countries are always coloured differently. Let’s assume that countries always consist of a single connected region — this disallows islands and would exclude some real-life regions like Palestine. Also, let us […]


Rather than a complete explanation, today is an excerpt from “Combinatorial Optimization” by Lex Schrijver; if for no other reason, because of the name (tied for best with the “hairy ball theorem”). A. Frank in 1982 showed the following ‘discrete sandwich theorem’ (analogous to the ‘continuous sandwich theorem’, stating the existence of a linear function […]


Consider the following network design problem. Schmoogle‘s 100 offices want to be able to stream huge amounts of data to each other (e.g., to broadcast talks to all their offices). In order to do this they need to connect all of their offices with new Phlogiston-net cabling. A single cable can be used to connect […]


From the dictionary in my head: Meta-Combinatorial Optimization (synonym: Combinatorial Combinatorial Optimization Optimization). n. To maximize or minimize some quantity of combinatorial optimization problems while respecting certain constraints. Examples. “After completing her PhD dissertation, `Planar Mouse Derangements,` Bella had to decide how to split the chapters of her thesis in to as many separate papers […]


My department, Combinatorics and Optimization, is hosting a conference this week in honour of its 40th anniversary. So things are about to get a little more nerdy on this blog as I will be mentioning some of the talk details. For today, at least: a picture! (click for big-ass pdf) It’s my contribution for today’s […]