Master of Mathematics in Combinatorics and Optimization - Co-operative Program (Discrete Optimization)

University of Waterloo

Discrete or combinatorial optimization embodies a vast and significant area of combinatorics that interfaces many related subjects. Included among these are linear programming, operations research, theory of algorithms and computational complexity. Much of combinatorial optimization is motivated by very simple and natural problems such as routing problems in networks, packing and covering problems in graph theory, scheduling problems, and sorting problems. But the methodology of the subject encompasses a variety of techniques ranging from elementary tree-growing procedures to constructions of Hilbert bases of integer lattices. The growth of this area has been linked with the development of linear programming and of graph theory over the last forty years. It also has close connections with the theoretical computer science, in particular, the analysis of algorithms. Generally the problems are to find efficient methods of constructing good solutions and to find methods of measuring the solution quality. That is, we wish to be able to produce bounds on the optimum solution which enable us to assert that the error of the solution in hand is no worse than, say, 2%. The C&O department has played a major role in the development of this area. During the seventies and eighties department members have made contributions to matching theory, polyhedral theory, combinatorial decomposition theory, minimax theorems for directed graphs, and oriented matroids. Currently, active work is being done on polyhedral combinatorics, approximation algorithms for NP-hard problems, semi-definite relaxations, extensions of matching and network flow theory, matroids and generalizations as well as on algorithmic game theory.