Programme

Some Topics in Combinatorial Optimization




The course will be held on alternate Wednesdays starting from February 4th, 2009
(February 4 and 18, March 4 and 18, April 1 and 15)

2:00pm - 5:00pm (CORE, room d-360)

In this course we will present some fundamental problems in combinatorial optimization. For each problem we will discuss applications and describe polynomial time combinatorial algorithms. Some polyhedral aspects will also be discussed. This course falls within the Graduate School in Systems, Optimization, Control and Networks (SOCN).

• Lecture 1: Introduction, Cardinality Matching Problem
  
  
• Lecture 2: Maximum Weight Matching Problem, Matching Polytope
  
  
• Lecture 3: Matroid Greedy Algorithm, Matroid Polytope
  
  
• Lecture 4: Matroid Intersection and Matroid Partitioning
  
  
• Lecture 5: Submodular Function Minimization
  
  
• Lecture 6: Approximation Algorithms: Edge Coloring, Traveling Salesman Problem
  
  

References:

- B. Korte, J. Vygens, "Combinatorial Optimization: Theory and Algorithms", Springer, 2000.
- G.L. Nemhauser, L.A. Wolsey, "Integer and Combinatorial Optimization", Wiley, 1988.