Math/AMath 514, Networks and Combinatorial Optimization, Autumn 2019

• Office : Padelford C-438
• Office hours : Monday 3-5 pm

• Office : Padelford C-8B
• Office hours : Tuesday 1-3 pm

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, and write mathematical proofs.
  
  
• Lecture : CMU 326, MW 9:00-10:15
  
  
• 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 class participation and homework assignments. It is crucial that homeworks are done by yourself. Homeworks are due weekly on (most) Wednesdays in class. Some announcements are only made in class and so please do not rely on just the information on this website to keep up with the class.
    
    
  • NO EXAMS

ASSIGNMENTS

• To read before the quarter starts : Chapter 6 in Schrijver's notes on "Problems, Algorithms and Running Times". Chapter 6 is essential for the whole course and can be read independently of all other chapters.
  
  
• Homework 1 (due in class on Wednesday Oct 2)
  Exercises from Chapter 1 of Schrijver's notes: 1.7, 1.8, 1.9, 1.11
  
  9/25: Reading: Section 1.4 in Schrijver's notes
  
  9/30: Reading: Section 10.1
  
  10/2: Reading: Section 2.1
  
  Homework 2 (due in class on Wednesday Oct 9)
  Exercises 10.1, 2.2, 2.4, 2.5
  
  10/7: Reading: Section 2.1,2.2
  
  10/9: Reading: Section 2.2,2.3
  
  Homework 2 (due in class on Wednesday Oct 16)
  Exercises 2.6(ii), 2.8, 2.16, 2.21
  
  10/14: Reading: Section 2.3, 2.4
  
  10/16: Reading: Section 2.4
  
  Homework 4 (due in class on Wednesday Oct 23)
  Exercises 2.23, 2.26, 2.27, 2.28
  for the last problem you can find the definition of C^* in problem 2.13
  
  10/21: Reading: Section 3.1, 3.2
  
  10/23: Reading: Section 3.3, 3.4
  
  Homework 5 (due in class on Wednesday Oct 30)
  Exercises 3.3, 3.11, 3.17, 3.19
  
  10/28: Reading: Section 3.6, 8.1, 8.2
  
  10/30: Reading: Section 8.2, 8.3
  
  Homework 6 (due in class on Wednesday Nov 13)
  Exercises 3.25, 8.4, 8.7, 8.14, 8.16
  
  11/13: Reading: Section 4.2, 8.4
  
  11/18: Reading: Section 4.3
  
  Homework 7 (due in class on Wednesday Nov 20)
  Problems 1.1, 1.2 (ii), 1.4, 1.5
  Explain why the model in used in problem 1.1 works
  
  11/20: Reading: Section 4.3, 4.5, 4.6
  
  Homework 8 (due in class on Wednesday !!! Dec 4 !!!)
  Exercises 4.7(ii), 4.9, 4.10, 4.11, 4.15, Explain why the model in Application 4.4 on pp 73 works.
  
  11/25: Reading: Applications of max flow (from Cook, Cunningham, Pulleyblank and Schrijver)