• Whole document: [1-437] (std · pr4 · pr1 · lec)
• Part 1. Organizational Matters [2-10] (std · pr4 · pr1 · lec)
  1. Contents [8-8]
  2. Literatur [9-10]
• Part 2. Linear Programming [11-217] (std · pr4 · pr1 · lec)
  1. Introduction to Linear Programming [12-52] (std · pr4 · pr1 · lec)
  2. Simplex Algorithm [53-76] (std · pr4 · pr1 · lec)
  3. Duality [77-116] (std · pr4 · pr1 · lec)
     1. Weak Duality [77-81] (std · pr4 · pr1 · lec)
     2. Simplex and Duality [82-84] (std · pr4 · pr1 · lec)
     3. Strong Duality [85-102] (std · pr4 · pr1 · lec)
     4. Interpretation of Dual Variables [103-109] (std · pr4 · pr1 · lec)
     5. Computing Duals [110-116] (std · pr4 · pr1 · lec)
  4. Degeneracy Revisited [117-132] (std · pr4 · pr1 · lec)
  5. Klee Minty Cube [133-147] (std · pr4 · pr1 · lec)
  6. Seidels LP-algorithm [148-166] (std · pr4 · pr1 · lec)
  7. The Ellipsoid Algorithm [167-217] (std · pr4 · pr1 · lec)
• Part 3. Approximation Algorithms [218-437] (std · pr4 · pr1 · lec)
  1. Introduction to Approximation [219-234] (std · pr4 · pr1 · lec)
  2. Integer Programs [235-248] (std · pr4 · pr1 · lec)
  3. Basic Techniques [249-275] (std · pr4 · pr1 · lec)
     1. Deterministic Rounding [249-252]
     2. Rounding the Dual [253-257]
     3. Primal Dual Technique [258-259]
     4. Greedy [260-265]
     5. Randomized Rounding [266-275]
  4. Scheduling on Identical Machines [276-289] (std · pr4 · pr1 · lec)
     1. Local Search [276-283]
     2. Greedy [284-289]
  5. Rounding Data + Dynamic Programming [290-336] (std · pr4 · pr1 · lec)
     1. Knapsack [290-294]
     2. Scheduling Revisited [295-307]
     3. Bin Packing [308-317]
     4. Advanced Rounding for Bin Packing [318-336]
  6. Randomized Rounding [337-373] (std · pr4 · pr1 · lec)
     1. MAXSAT [337-358]
     2. MAXCUT [359-373]
  7. Primal Dual Techniques [374-407] (std · pr4 · pr1 · lec)
     1. Primal Dual Revisited [374-380]
     2. Feedback Vertex Set for Undirected Graphs [381-388]
     3. Primal Dual for Shortest Path [389-395]
     4. Steiner Forest [396-407]
  8. Cuts & Metrics [408-421] (std · pr4 · pr1 · lec)
  9. TSP [422-437] (std · pr4 · pr1 · lec)