MCS 521: Combinatorial Optimization

MCS 521

Spring 2022

Monday-Wednesday-Friday, 10:00 - 10:50 am BSB 337

Instructor

Will Perkins

willp@uic.edu

Office: SEO 626

Office Hours: TBA

Course Information

Main Topics of the Course:

Algorithms for trees and paths
Max flow problems
Matching algorithms
Travelling Salesman problem
Linear programming duality
Approximation algorithms

Syllabus

References

Required textbook: Combinatorial Optimization, Cook, Cunningham, Pulleyblank, Schrijver.
Useful reference: Combinatorial Optimization: Exact and Approximate Algorithms, Trevisan.

Schedule

Jan 10What is combinatorial optimization?
Jan 12Minimum spanning trees
Jan 14MST and linear programs
Jan 19Shortest paths, Ford's algorithm