Math 523 Section 201
Introduction to Combinatorial Optimization
Online Course Material 


Happy New Year.

Notes look authoritative when typed so be wary. They may look perfect but may still contain errors! I don't have an editor.
I arrive most days by 9:00. I typically do not read my email from home (i.e. evenings and weekends).

Our class is scheduled 11-12 MWF in MATH 225. On Friday Jan 7 we had the 2 hour lecture summary of MATH 340. Hope it was helpful but feel free to ask questions. Some of the material is posted on my MATH 340 website. I will be missing 3 wednesday meetings (Jan 19, Feb 23, Mar 30) and will have to reschedule for those times.

  • Course Outline: grading etc. 
  • Assignment 1 due Monday Jan 24.  
  • Assignment 2 due Monday Feb 7.  
  • Assignment 3 due Friday Feb 25.  
  • Assignment 4 due Friday Mar 18.  
  • Assignment 5 due Wednesday April 6.  
  • Network Flow algorithm published in Operations Research vol 41 (1993), 338-350  
  • Weighted Matching algorithm using the primal dual algorithm described in Papadimitriou and Steiglitz but with a more useful example. The example in the book does not require blossoms and so could be solved by a minimum cost flow problem on the associated `bipartized' graph.  
  • Fractional to Integral Strategy We show that solving minimum cost flow problem on the associated `bipartized' graph enables one to obtain quite a reasonable solution to the weighted graph problem. In this case I have phrased it in terms of f-factors.  
  • A comic for your amusement. There must be many others of course.