COMP 150-CO
Combinatorial Optimization
FALL 2005

Instructor: Lenore Cowen
Halligan 237; 7-5134; cowen@cs.tufts.edu; Office Hours: T 6:00-6:50pm, or by appointment.
Lectures: Tuesdays 7-10pm in Halligan Hall Rm 108.

TA: Arthur Brady; abrady@cs.tufts.edu; Office hours TBA.

Description: Linear programming, including duality theory, simplex and interior point methods; matchings, network flows, matriods, Integer programs; applications in transportation and scheduling.

Grading: Grades will be based on weekly hw assignments.

Rough syllabus: (subject to change)

• September 6: Introduction to LP / bipartite matching
  For the matching material, see also these supplementary notes: part I (ps format) or pdf format and part II (ps format) or pdf format
• September 13: Shortest Paths (Chapter 2)
• September 20: Max flow/Min cut I (Chapter 3)
• September 27: Linear Programming I
• October 4: Linear Programming II
• Oct 11: NO CLASS, Tufts on a MONDAY schedule
• October 17: Minimum Cost Flow problems (Chapter 4)
• October 25: Min cost circulation problems (Chapter 4 cont)
• November 1: Weighted Bipartite Matchings
• November 8: Matching Theory (Chapter 5)
• November 15: Integer programs and Approximation Algorithms
• November 22: Traveling Salesman Problem
• November 29: TBA
• December 6: Matroids

Prerequisites: Comp 160 and Linear Algebra or permission of the instructor.

Text: Combinatorial Optimization by Cook, Cunningham, Pulleybank and Schrijver, Wiley, 1998.