MCS 521: Combinatorial Optimization

MCS 521

Spring 2020

Tuesday, Thursday, 9:30 - 10:45 am LH 107

Instructor

Will Perkins

willp@uic.edu

Office: SEO 626

Office Hours: Thursdays 10:45am-12:45pm, or by appointment

Course Information

Main Topics of the Course:

  1. Algorithms for trees and paths
  2. Max flow problems
  3. Matching algorithms
  4. Travelling Salesman problem
  5. Linear programming duality
  6. Approximation algorithms

References
Schedule
  • Jan 14What is combinatorial optimization?

  • Jan 16Minimum spanning trees

  • Jan 21MST and linear programs

  • Jan 23Shortest paths, Ford's algorithm

  • Jan 28Bellan-Ford algorithm

  • Jan 30Max-flow Min-cut Theorem

  • Feb 4Algorithms for Max Flow

  • Feb 6Maximum Bipartite Matching

  • Feb 11Push-relabel max flow algorithm

  • Feb 13Push-relabel max flow algorithm

  • Feb 18Min cuts in undirected graphs

  • Feb 20

  • Feb 25

  • Feb 27

  • Mar 3

  • Mar 5

  • Mar 10

  • Mar 12

  • Mar 17

  • Mar 19

  • Mar 31

  • Apr 2

  • Apr 7

  • Apr 9

  • Apr 14

  • Apr 16

  • Apr 21

  • Apr 23

  • Apr 28

  • Apr 30