409 - Discrete Optimization - Winter 2025

Course information

• Class schedule: MWF 9:30am - 10:20am in MEB 246
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: We 11-12 in PDL C440.
  
• TAs:
  
  • Rainie Bozzai. Office hour: Thursdays 8:30am-9:30am on Zoom.
• Topics to be covered: computational complexity, minimum spanning trees, shortest paths, max flow problems, min cost flow problems, matchings, traveling salesman problem, integrality of polytopes.
• Prerequisites : This course requires a good working knowledge of Math 407 (Linear Programming) and Math 308 (Linear Algebra).
  
• Grading: The grade will be a convex combination of the performance in the submitted problem sets (20%; lowest scoring assignment is dropped), the mid term exam (30%) and the final exam (50%).
• Problem sets: Problem sets will be posted each Friday; due date is the following Friday 11pm via GradeScope.
  Late policy: GradeScope will accept submissions until Monday 11pm. Every student is allowed 6 late days in total. So you are allowed to submit for example 6 assignments up to 24h late or two assignment 3 days late. No prior approval required. Simply submit to GradeScope when you are done. If you submit late and you are out of late days the submission counts 0.
  Collaboration policy: You are allowed (in fact encouraged) to discuss the homework problems in groups. You may submit the solutions in groups up to 3. Each group is required to write up their own solutions. Absolutely identical submission will be considered as a violation of this policy. AI may not be used. You may not use pre-existing solutions from the internet or elsewhere.
  
• Lecture notes for the course are available here
• Discussion forum: Other than in office hours, you may ask questions on course content and homework on the course discussion forum on Ed. 
• Religious Accommodations: Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UWs policy, including more information about how to request an accommodation, is available at https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/. Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form, see https://registrar.washington.edu/students/religious-accommodations-request/.

Covered material

1. Monday, Jan 6, 2025: First day of class. Logistics + Chapter 1.1 on "Algorithms and Complexity"
2. Wednesday, Jan 8, 2025: Graph Theory
3. Friday, Jan 10, 2025: TSP. Started with Chapter 2 on spanning trees.
4. Monday, Jan 13, 2025: Minimum spanning trees
   
5. Wednesday, Jan 15, 2025: Finished Chapter 2 on spanning trees. Just started with Chapter 3 on shortest paths.
6. Friday, Jan 17, 2025: Dijkstra's algorithm with example. Stopped in middle of correctness proof of Dijkstra's algorithm.
7. Monday, Jan 20, 2025: NO CLASS (MLK Day)
   
8. Wednesday, Jan 22, 2025: Finished analysis of Dijkstra. Then Moore-Bellman-Ford algorithm.
9. Friday, Jan 24: Detecting negative cost cycles
10. Monday, Jan 27: Beginning of Network flow chapter until Ford-Fulkerson algorithm
11. Wednesday, Jan 29: MaxFlow=MinCut Theorem with proof
12. Friday, Jan 31: Edmonds-Karp. Beginning of bipartite matching
13. Monday, Feb 3: Koenig's Theorem + Halls Theorem
    
14. Wednesday, Feb 5: Beginning of Linear programming chapter
    
15. Monday, Feb 10: Hyperplane separation theorem.
16. Wednesday, Feb 12: MIDTERM
17. Friday, Feb 15: Farkas Lemma, Strong Duality Theorem, Complementary slackness
18. Monday, Feb 17: NO CLASS (Presidents' Day)
19. Wednesday, Feb 19: Algorithms for linear programming. Integer programs.
20. Friday, Feb 21: Integer hulls. Total unimodularity.
21. Monday, Feb 24: Matching polytope for bipartite graphs is integral.
22. Wednesday, Feb 26: TUness of node-edge incidence matrices of directed graphs.
23. Friday, Feb 28: TUness of matrices with consecutive ones property. Beginning of Branch & Bound chapter.
    

Problem sets

• Homework 1. Due: Friday, Jan 17, 11pm on GradeScope.
• Homework 2. Due: Friday, Jan 24, 11pm on GradeScope.
• Homework 3. Due: Friday, Jan 31, 11pm on GradeScope.
• Homework 4. Due: Friday, Feb 7, 11pm on GradeScope.
• Homework 5. Due: Friday, Feb 21, 11pm on GradeScope.
• Homework 6. Due: Friday, Feb 28, 11pm on GradeScope.
• Homework 7. Due: Friday, Mar 7, 11pm on GradeScope.
  

Midterm exam

• Wednesday, Feb 12, 2025 in class (i.e. 9:30am-10:20am in MEB 246). You may bring one sheet of notes (printed on one side or handwritten on both sides).

Final exam

• Wednesday, Mar 19, 2025, 8:30am - 10:20am in MEB 246. You may bring one sheet of notes (printed on both sides or handwritten on both sides).

Text books

• "Combinatorial Optimization" by Cook, Cunningham,Pulleyblank, Schrijver: Contains most topics that are also covered in class (plus many more). A very readable, though quite expensive book.
  
• "Computational complexity" by Arora and Barak: State of the art book for complexity theory. From the topics covered in class, this book contains only the small complexity part. A preliminary version is available for free here.

Corrections to the lecture notes

• Jan 6, 2025: Minor typos in Chapter 1.