Algorithms, algorithmic paradigms, and algorithmic tools for provably solving combinatorial optimization problems. Emphasis on graph optimization and discussion of approaches based on linear programming and continuous optimization. Potential optimization problems include both polynomial time solve-able problems, e.g., maximum flow, minimum cost flow, matching, assignment, minimum cut, matroid optimization, submodular function minimization, and NP-hard problems, e.g., Steiner trees, traveling salesperson, maximum cut. Potential paradigms and tools include: linear programming, multiplicative weight update method, algebraic methods, and spectral methods. Prerequisite: CS 161 or equivalent.
3 units · Letter or Credit/No Credit
Algorithms, algorithmic paradigms, and algorithmic tools for provably solving combinatorial optimization problems. Emphasis on graph optimization and discussion of approaches based on linear programming and continuous optimization. Potential optimization problems include both polynomial time solve-able problems, e.g., maximum flow, minimum cost flow, matching, assignment, minimum cut, matroid optimization, submodular function minimization, and NP-hard problems, e.g., Steiner trees, traveling salesperson, maximum cut. Potential paradigms and tools include: linear programming, multiplicative weight update method, algebraic methods, and spectral methods. Prerequisite: 161 or equivalent.