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 20Gomory-Hu cut trees

  • Feb 25TSP Approximation algorithms

  • Feb 27Set Cover Approximation

  • Mar 3Linear Programming

  • Mar 5Rounding Linear Programs

  • Mar 10Maximum Matchings

  • Mar 12Maximum Matchings

  • Mar 31The Blossom algorithm

  • Apr 2Min weight perfect matchings

  • Apr 7Integrality of polyhedra

  • Apr 9Facets of polytopes

  • Apr 14Goeman's-Williamson algorithm

  • Apr 16SDP's and approximate coloring

  • Apr 21Lovasz Theta Function

  • Apr 23TSP, Held-Karp

  • Apr 28Subtour LP for TSP

  • Apr 30Matroids