Math 514, Network Optimization, Autumn 2009

• Office : Padelford C-438
• Phone : (206) 616 9374
• E-mail : rrthomas (at) u (dot) washington (dot) edu
• Office hours : TBA

Course Information

• Description : This is a graduate class on the fundamentals of network optimization (aka combinatorial optimization). The majority of these problems involve finding the "best" candidate among a set of objects associated with a network/directed graph. Many of these problems come from real-world applications and as such it is important to solve large instances of these problems in practice. Therefore, along with understanding the mathematical structure of the problems, we will also be interested in algorithms for solving them and the complexity/difficulty of these algorithms from a computer science point of view. There will be a small final project that involves coding an appropriate algorithm that we will learn in class or reading and summarizing a research paper in this area.
  
  Main topics to be covered: : We will look at various graph problems and their algorithms such as finding minimum spanning trees, shortest paths, max/min flow, min cut, matchings, optimal assignment, and the travelling salesman problem. The first set of problems have combinatorial graph theoretic algorithms and are "easy" in a complexity sense. The last few problems are "hard" and require techniques beyond combinatorics. To deal with these we will learn the basics of linear programming and then some integer programming. Using these advanced, more geometric methods, we will get a sense of how the hard problems are modeled and solved in practice whenever their sizes allow them to be tackled effectively. An important companion to an algorithm is its complexity. We will learn some elementary complexity theory in order to be able to analyze the algorithms we learn.
  
  
• Lecture : Mary Gates Hall 234, MWF 9:30-10:20
  
  
• Textbook : The official textbook for the class will be "Network Flows and Monotropic Optimization" by R.T. Rockafellar.
  
  
• Required Work:
  • There will be daily reading assignments from the book. I will cover essentials but many of the details and discussions will be left as reading assignments.
  • There will be five homework assignments (roughly once every other week) which will carry 80% of the grade.
  • There will also be a final project to be specified later that will carry 20% of the grade.
  • NO EXAMS

Daily assignments:

• Show that any minimum spanning tree (mst) problem can be reduced to a mst problem with positive edge costs.
• Let H be a spanning connected subgraph of G. Argue that H is a spanning tree in G if and only if H has exactly n-1 edges where n is the number of vertices in G.
• Let T be a spanning tree in a graph G, e and edge in G that is not in T, and f be an edge in a path in T between the end points of e. Show that the graph obtained from T by deleting f and adding e is again a spanning tree in G.
• Establish the validity of Kruskal's algorithm.

Projects: