CS 261 Combinatorial Optimization



Topics: algorithms for optimization problems such as matching, max flow, min-cut and load balancing. Using linear programming, emphasis is on LP duality for design and analysis of approximation lgorithms.Approximation algorithms for NP-complete problems such as Steiner trees, traveling salesman and scheduling problems. Randomized algorithms. 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.
Course period02/4/12 → …
Course level200