Prerequisite: familiarity with discrete algorithms at the level of CS 260. Topics: Maximum flow, minimum cut. Polytopes, linear programming, LP-relaxation, rounding. Greedy algorithms, matroids. Approximation algorithms for NP-complete problems. Randomized algorithms. These techniques are applied to combinatorial optimization problems such as matching, scheduling, traveling salesman, set cover, maximum satisfiability.