Math/AMath 514, Network Optimization, Autumn 2013

• Office : Padelford C-438
• Phone : (206) 616 9374
• E-mail : rrthomas (at) uw (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. This is a rigorous mathematical introduction to network optimization with proofs. Students are expected to solve both theoretical and practical problems in homework.
  
  
• Lecture : Padelford Hall C-401, MWF 9:30-10:20
  
  
• Textbook : There is no official textbook for the class. The lectures will follow notes written by Lex Schrijver that you can find here. You are encouraged to read additional materials to help your understanding. Here are some of the popular books on combinatorial optimization that you can consult as needed:
  
  
• Additional References :
  
  • J. Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.
  • W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization.
  • C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 19 82.
  • B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 S pringer, Berlin Heidelberg New York, 2006.
  • 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.
  
  
• 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.
  • Your grade will be based on homework assignments. Homeworks are due weekly on Fridays in class. I will post a few problems after each lecture. The last set of problems on a given homework will be posted after the Monday lecture of the week in which the homework is due.
  • NO EXAMS

LECTURES and ASSIGNMENTS