COMP/MATH 552 : Combinatorial Optimization


Instructor: Yaqiao Li
Contact: yaqiao dot li at mail dot mcgill dot ca
Office Hours: Monday 3:00 - 4:00 pm, or by appointment
Office: McConnell 303

Term: Winter 2018, Jan. 08 - Apr. 16.
Lectures: Tuesdays and Thursdays 08:35 - 09:55 am in McConnell 103
Study Break: March 5 - 9, no lectures.

Teaching Assistant: Mashbat Suzuki
Contact: mashbat dot suzuki at mail dot mcgill dot ca
Office Hours: Thursday 11:00 am - 1:00 pm.
Office: McConnell 303


Course outline

Prerequisites:

Math 350 (Graph theory and Combinatorics) or COMP 362 or equivalent. This course is intended for graduate students and senior undergraduate students in math or computer science.
The main prerequisite is mathematical maturity, with basic knowledge in graphs and linear algebra. The exposure to some algorithms (e.g. shortest path, minimal spanning tree, bipartite matching, max flow - min cut) is preferable, though not essentially required. It is important that you feel comfortable or are ready to work with rigorous mathematical reasoning.

Course description:

Combinatorial optimization is a branch of mathematics that studies optimization over a finite set that usually can be described by a graph or other combinatorial object. It has wide application in sciences and engineering.
This is an introductory course on combinatorial optimization. Our focus will NOT be on modelling practical problems, but on structure and theory behind those problems and algorithms. The course mainly consists of: polyhedral combinatorics and application in general matching theory; matroids; equivalence of optimization and separation; and submodular optimization. A recurring theme in this course is to see individual problems are unified in general theory.
See tentative topics for things that are planned to be covered. Topics (certainly also interesting and important!) that won't be covered include but not limited to: heuristic algorithms, approximation algorithms, semidefinite programming, complexity, etc.

Evaluation:

There are no formal mid-term or final exams. Evaluation will be made through assignments, in-class tests and a final project.
Assignments: 30%. (Three assignments, each worth 10%)
In-class Tests: 40%. (Two tests, each worth 20%) : Test 1 on Feb. 22nd, Test 2 take home.
Project: 30%.

Assignments:


Projects:


Course references:

There is no one single text book. The main references will be the following (increasing level) together with other materials that will be issued with the lectures.

Tentative topics:

It should be noted that the topics are subject to change depending on the interest of the audience, and longer or shorter treatment of specific topics.

Lectures: