1 - 3 of 3 results for: CS261

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.

This course is motivated by problems for which the traditional worst-case analysis of algorithms fails to differentiate meaningfully between different solutions, or recommends an intuitively "wrong" solution over the "right" one. This course studies systematically alternatives to traditional worst-case analysis that nevertheless enable rigorous and robust guarantees on the performance of an algorithm. Topics include: instance optimality; smoothed analysis; parameterized analysis and condition numbers; models of data (pseudorandomness, locality, diffuse adversaries, etc.); average-case analysis; robust distributional analysis; resource augmentation; planted and semi-random graph models. Motivating problems will be drawn from online algorithms, online learning, constraint satisfaction problems, graph partitioning, scheduling, linear programming, hashing, machine learning, and auction theory. Prerequisites: CS161 (required). CS261 is recommended but not required.