MATH 566 - Discrete Optimization

Instructor: Bernard Lidick√Ĺ
Office: 422 Carver Hall
email: lidicky -at- iastate.edu
Office hours: ??

Section: 2
Where: LAGOMAR 1520
When: Tue Thu 12:30 PM - 1:45 PM
Final exam: TBD
Syllabus

Homework

  1. HW 1 - Feed ME (cheaply)

Lecture Log

  1. Aug 21 Linear programming
  2. Aug 23 Geometry and Linear programming Duality introduction

  3. Aug 28 Duality Inteprertaion Separation Theorem
  4. Aug 30 Farkas Lemma

  5. Sep 4 Consequenced of Duality Simplex Method
  6. Sep 6 Klee-Minty Cube and Ellipsoid Method

  7. Sep 11 Interior Point Methods
  8. Sep 13 Minium Spanning Tree

  9. Sep 18 Shortest Path
  10. Sep 20 l13 - Shortest Path and Linear Programming

  11. Sep 25 l14 - Network Flows - First Intro
  12. Sep 27 l15 - Network Flows - first algorithm

  13. Oct 2 l16 - Network Flows - Faster Algorithm
  14. Oct 4 l17 - Minimum Cuts in Unidrected Graphs

  15. Oct 9 l18 - Gomory-Hu Trees
  16. Oct 11 l19 - Minimum Cost Flow

  17. Oct 16 l20 - Minimum Mean Cycle
  18. Oct 18 l21 - Integer Programming - Unimodularity

  19. Oct 23 l22 - Integer Programming - Branch and bound
  20. Oct 25 l23 - Integer Programming - Cutting Planes

  21. Oct 30 l24 - Matchings
  22. Nov 1 l25 - Weighted Bipartite Matchings

  23. Nov 6 l26 - Weighted Matching - Goemans-Williamson
  24. Nov 8 l27 - Travelling Salesman Problem

  25. Nov 13 l28 - Semidefinite Programming
  26. Nov 15 l29 - Max-Cut

  27. Nov 20 Thanksgiving
  28. Nov 22 Thanksgiving

  29. Nov 27 l30 - Matroids
  30. Nov 29

  31. Dec 4
  32. Dec 6