CAS 746 - Advanced Topics in Combinatorial Optimization


Tuesday 13:30-16:20 in ITB 222

Slides 1: Introduction using Peg Solitaire as an illustartion
Slides 2: Tim Evans' Quantum Field Theory Course
Slides 3: Optimization Algorithms
Slides 4: Combinatorial Optimization


Antoine Deza
Office: ITB 127
Extension: 23750
Office hours: Tuesday 16:30-17:20 or by appointment

Course Outline

Combinatorial optimization deals with the design and analysis of algorithms for finding the best or an approximate solution to problems which have a discrete structure. This course provides an introduction to useful frameworks for discrete optimization problems. We introduce the basic concepts of polyhedra, lattices and integer cones and illustrate these notions by some examples coming from combinatorial optimization. In this course we are also concerned with computational issues and the analysis of algorithmic performances. Open questions dealing with optimizaton algorithms, diameter of polytopes, Minkowski sums, and degree sequences of hypergraphs are presented and discussed. The course will be relatively self-contained. Reading will be assigned to cover some of the topics.

The instructor and university reserve the right to modify elements of the course during the term. The university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given with explanation and the opportunity to comment on changes. It is the responsibility of the student to check their McMaster email and course websites weekly during the term and to note any changes.


Students with disabilities can receive accommodations to assist them in the completion of assignments and exams. Please contact the Centre for Student Development ( for advice and for arranging assistance. Students are also encouraged to talk to the instructor about this issue.


"The Faculty of Engineering is concerned with ensuring an environment that is free of all adverse discrimination. If there is a problem that cannot be resolved by discussion among the persons concerned individuals are reminded that they should contact the Department Chair, the Sexual Harassment Officer or the Human Rights Consultant, as soon as possible."

Academic Dishonesty

"Students are reminded that they should read and comply with the Statements on Academic Ethics and the Senate Resolutions on Academic Dishonesty as found in the Senate Policy Statements distributed at registration and available in the Senate Office."
Created by