Bertrand Guenin

Characterizing classes of linear programs

Bertrand Guenin’s general area of interest is combinatorial optimization and in particular, the problem of characterizing classes of linear programs which have optimal integer solutions. This is motivated by the fact that the existence of such optimal integer solutions are the basis of many of the most celebrated combinatorial algorithms, moreover, many purely combinatorial questions can be stated in this framework.

Bertrand is interested in structural problems: “Suppose I wish to characterize a family of objects which satisfies some mathematical property, I would first try to identify natural elementary classes, and then show that every object in that family can be constructed from objects in these elementary classes”.

Bertrand has applied this framework to flow and colouring problems. Flow questions are concerned with the transfer of commodities. The celebrated maximum flow, minimum cut theorem states that the maximum amount of a commodity that can be shipped between two locations across a network is equal to the size of the smallest bottleneck separating these locations. This result does not always extend to the cases where we consider more than one commodity at the time, or to flows in matroids. Bertrand is interested in finding a precise characterization of the class of objects for which this theorem extends. Another topic of investigation of Bertrand is to find generalizations of the four colour theorem which states that every map can be coloured using only four colours.

University of Waterloo Mathematics, Annual Report 2005