Combinatorial Optimization, MATH 4320/5320.

Dalhousie University,

Department of Mathematics and Statistics

• An airline wants to assign crew and aircraft to its flights,and get everyone home at the end of the day.
• A cellular phone service provider wants to assign radio frequencies to its transmitters so that interference is minized and the radio spectrum is optimally used.
• A cable company wants to lay cable to connect all its subscribers at minimal cost.
• The registrar wants to schedule exams without conflicts.
• A dairy company wants to assign cost-efficient pickup routes for its milk trucks.

These are all examples of combinatorial optimization problems. A simple, but costly approach to solving such problems would be to
enumerate all possible solutions (schedules, routes, assignments), and select the best one. In some cases we cannot do better, given the current realities of computing. For many other cases, ideas from Discrete Mathematics have led to fast and efficient solution methods.

In this course, you will be introduced to major combinatorial optimization problems such as maximum flow, minimum spanning tree,
minimum cost matching and travelling salesman.  You will learn elegant algorithms to solve well-behaved problems, and see how to approach intractable problems with a mixture of intuition and theory.

This is a theoretical course, with an accent on formal definition and rigorous analysis of the methods.  However, we will see abundant
evidence of the relevance of the material to concrete, modern applications.

Prerequisites: Math 2002 and 2040, or permission from the instructor.