This course gives an in-depth introduction to the field of combinatorial optimization. Much of
our focus is on geometric and algorithmic methods for attacking combinatorial optimization problems.
We study basic polyhedral theory, structured matrices (totally unimodular, balanced, perfect, ideal), matroids and submodularity.
We also extend results from basic algorithms courses to settings which require more machinery. Some examples include
(i) finding shortest paths with negative cost edges in directed graphs can be solved easily via the Bellman-Ford Algorithm. In
undirected graphs, we need to study T-joins, (ii) finding minimum cost spanning trees can be done via the greedy method, but how do you
find a shortest cost arborescence in a directed graph? (iii) representing minimum cuts via Gomory-Hu Trees,
(iv) the so-called Hungarian method finds maximum weight matchings in bipartite graphs; in general graphs, it requires one
of the most sophisticated primal-dual algorithms.
The intended prerequisites are Math 350 or Comp 362 or equivalent. Basic familiarity with graphs, algorithms, running times,
and linear programming (not the Simplex algorithm, just LP duality) is desirable. No formal experience
with these topics is strictly needed, but a strong mathematical background is definitely necessary.
This course is primarily aimed at higher
level undergraduate and graduate students in mathematics or computer science.
1. Right to submit in English or French written work that is to be graded [approved by Senate on 21 January 2009]:
In accord with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.
The right applies to all written work that is to be graded, from one-word answers to dissertations, except in courses in which acquiring proficiency in a language is one of the objectives.
The statement is not needed for courses in which students do not submit written work that is to be graded.
Instructors who cannot grade French written work should consult their Chair/Director or Dean, in faculties without departments, to make arrangements for grading French submissions.
2. Academic Integrity statement [approved by Senate on 29 January 2003]:
McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the
Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/students/srr/honest/ ) for more information).
You may use this FRENCH TRANSLATION of the Academic Integrity statement on your course outlines as you see fit:
L'université McGill attache une haute importance à l’honnêteté académique. Il incombe par conséquent à tous les étudiants de comprendre ce que l'on entend par tricherie, plagiat et autres infractions académiques,
ainsi que les conséquences que peuvent avoir de telles actions, selon le Code de conduite de l'étudiant et des procédures disciplinaires (pour de plus amples renseignements,
veuillez consulter le site www.mcgill.ca/students/srr/honest/ ).
Please note that failure by an instructor to include a statement about academic integrity on a course outline shall not constitute an excuse
by a student for violating the Code of Student Conduct and Disciplinary Procedures [Senate, 29 January 2003]. Nonetheless, it is important that all instructors do indeed include the statement.
The links found directly below will lead you to relevant resource documents regarding Academic Integrity that you may find helpful in planning a class discussion on issues related to academic integrity.
Both at the beginning of your course and when assigning papers, essays or lab reports, engaging students in such discussions is a positive way to foster an ethos of integrity that is vital to our teaching and research missions.
The documents may also help you raise issues of academic integrity with your graduate students and research assistants. You might consider discussing it with them as a group or individually
as appropriate to your discipline and the student's program.
3. Use of Text-matching software [approved by Senate on 1 December 2004]:
Instructors who want to use text-matching software to verify the originality of students’ written course work must register for use of the software with Teaching Technology
Services (Maggie.email@example.com ) and must inform their students before the drop/add deadline, in writing, of the use of text-matching software in a course.