COMBINATORIAL OPTIMIZATION


Math 552/Comp 552 - Winter Term, 2010.

General Information.

  • Course Instructor
  • Lectures
  • Overview
  • Prerequisites
  • Textbooks
  • Assignments
  • University Policies


    Instructor.

  • Prof. Bruce Shepherd
  • Telephone: 398-4578
  • Office: Room 1113, Burnside Building
  • Office hours: Tuesday, Thursday 230-330, or by email appt.
  • Lectures Tues/Thus 1-230.
  • Email: bruce.shepherd at mcgill dot ca
  • Top

    Lectures.

  • Time: Tuesday and Thursday: 1-230.
  • Location: Room 920, Burnside Hall
  • Top

    Overview.

    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.
    Top

    Tentative Lecture List.

    A list of lectures will be here.
    A list of lectures from the last time the course was offered (2010) can be found here.
    Top

    Pre-requisites.

    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.
    Top

    Textbooks.

    The main course reference texts are:
    Combinatorial Optimization by B. Korte and J. Vygen. Fifth Edition
    A Course in Combinatorial Optimization by A. Schrijver
    Combinatorial Optimization by W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver.
    Combinatorial Optimization: Polyhedra and Efficiency by A. Schrijver


    Other helpful references:
    Notes on LP, Convexity, Polyhedra and more
    Algorithms by S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani
    Intro to Complexity by G. Brightwell, B. Shepherd
    Graph Theory with Applications by J.A. Bondy and U.S.R. Murty
    Top

    Assignments.

    Course grades will be based upon assignments (35%), in-class quizzes (35%) and a take-home final exam (30%).
    Top



    University Policies.

    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.
    RESOURCE DOCUMENTS
    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.
    www.mcgill.ca/files/students/AI-InstructorsResource.pdf
    www.mcgill.ca/files/students/AI-InstructorsResourceGraduateStudents.pdf

    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.lattuca@mcgill.ca ) and must inform their students before the drop/add deadline, in writing, of the use of text-matching software in a course.
    RESOURCE DOCUMENT
    www.mcgill.ca/files/students/Text-Matching-Policy-on-English.pdf