• Whole document: [1-483] (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-258] (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)
  8. Karmarkars Algorithm [218-258] (std · pr4 · pr1 · lec)
• Part 3. Approximation Algorithms [259-483] (std · pr4 · pr1 · lec)
  1. Introduction to Approximation [260-275] (std · pr4 · pr1 · lec)
  2. Integer Programs [276-289] (std · pr4 · pr1 · lec)
  3. Basic Techniques [290-316] (std · pr4 · pr1 · lec)
     1. Deterministic Rounding [290-293]
     2. Rounding the Dual [294-298]
     3. Primal Dual Technique [299-300]
     4. Greedy [301-306]
     5. Randomized Rounding [307-316]
  4. Scheduling on Identical Machines [317-330] (std · pr4 · pr1 · lec)
     1. Local Search [317-324]
     2. Greedy [325-330]
  5. Rounding Data + Dynamic Programming [331-377] (std · pr4 · pr1 · lec)
     1. Knapsack [331-335]
     2. Scheduling Revisited [336-348]
     3. Bin Packing [349-358]
     4. Advanced Rounding for Bin Packing [359-377]
  6. Randomized Rounding [378-414] (std · pr4 · pr1 · lec)
     1. MAXSAT [378-399]
     2. MAXCUT [400-414]
  7. Primal Dual Techniques [415-448] (std · pr4 · pr1 · lec)
     1. Primal Dual Revisited [415-421]
     2. Feedback Vertex Set for Undirected Graphs [422-429]
     3. Primal Dual for Shortest Path [430-436]
     4. Steiner Forest [437-448]
  8. Hardness of Approximation [449-483] (std · pr4 · pr1 · lec)