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