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.