MATH 523 Combinatorial Optimization 2017 fall 

 

Instructor: Jozsef Solymosi,

Office: MATH 220,

solymosi@math.ubc.ca 

 

Grading: Homework assignments 40%, Take home midterm 20%, take home final 40%. 

 

TueThu: 14:00 AM to 15:30 PM in MATX-1118


 

Office hours:  by appointment (send me an email)

 

Topics: 

 

 Shortest paths and trees

o Shortest paths with nonnegative lengths 

o Dijkstra’s algorithm 

o Minimum spanning trees 

o Traveling salesman’s problem 

 

 Polytopes, polyhedra, Farkas’ lemma, and linear programming

o Convex sets 

o Polytopes and polyhedra 

o Farkas’ lemma 

o Linear programming 

 

 Matchings and covers in bipartite graphs

o Matchings and covers 

o Augmenting paths 

o Koenig’s theorems 

 

 Menger’s theorem, flows, and circulations

o Menger’s theorem 

o Flows in networks 

o Finding a maximum flow 

 

 Semidefinite Programming (selected topics)

 

Notes: 

 “Understanding and Using Linear Programming” and “Approximation Algorithms and Semidefinite Programming” by J.Matousek and B.Gartner, Springer. UBC library eBooks 

• A. Schrijver, “A Course in Combinatorial Optimization” Schrijver 

• L. Lovasz, “Semidefinite optimization” Lovasz 

 

Further readings:

o  Beating Christofides by Sitters and Stougie



Problem sets:

  1. TSP&3SAT Due Sept 21


  2. Midterm