Combinatorial Optimization

  • Instructor: Dr. Tibor JORDAN
  • Contact:
  • Prerequisites: Familiarity with the basics of graph theory and linear algebra is useful.
  • Text: classnotes, handouts, and A. Schrijver, A course in combinatorial optimization (2009)

Course description:

Topics covered:

  • Exploring a graph: breadth-first search (BFS), depth-first search (DFS), and their applications
  • Shortest path algorithms in digraphs (Dijkstra, Bellman-Ford)
  • Minimum length spanning trees - the greedy algorithm
  • Minimum cost arborescence algorithm
  • Eulerian graphs and digraphs, orientations of graphs and mixed graphs
  • Matchings in bipartite graphs - theorems of K?onig and Hall
  • Maximum cardinality and maximum weight matching algorithms in bipartite graphs
  • Edge colorings, timetables, another theorem of K?onig
  • Menger's theorem, Network flows, Max-flow Min-cut theorem
  • Flow algorithms by Ford and Fulkerson, and by Edmonds and Karp; Minimum cost flows
  • The assignment problem and the transportation problem
  • Circulations, Hoffman's theorem
  • Matchings in general graphs - Tutte's theorem, the Tutte-Berge formula
  • Maximum cardinality matching algorithm in general graphs
  • Computing the edge-connectivity of graphs
  • Flow- and Cut-equivalent trees
  • Chordal graphs, maximum weight stable sets in chordal graphs
  • Approximation algorithms - the traveling salesman problem, the Steiner tree problem
  • Minimum multiway cut, minimum k-cut, multicut in trees
  • Facility location problems
  • Basics of Linear Programming
  • Dynamic Programming techniques
  • Scheduling problems on parallel machines