MATH 523 Combinatorial Optimization 2017 fall 


Instructor: Jozsef Solymosi,

Office: MATH 220, 


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)




 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)



 “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. LP Due Oct 5
  3. NPC reductions Due Nov 2
  4. Random Due Nov 23
  5. Final