CSc 85020: Combinatorial Algorithms: This is a course on combinatorial algorithms (or, as some would say, algorithms), covering topics beyond the scope of the first-year algorithms class. More precisely, this is an advanced course in algorithms for optimization problems concerning discrete objects, principally sets and graphs, though much of it involving linear programming (LP), either implicitly or explicitly. In these problems we’re searching a finite but exponentially large set of feasible solutions (e.g., all possible matchings in a graph) for one maximizing or minimizing some objective function. (More generally, in linear optimization we’re optimizing over a polytope in $R^n$.) Nonetheless, most of the problems in this course are optimally solvable in polynomial time: shortest paths and spanning trees, matchings, flows and cuts, and LP itself. (Or, as in the case of certain kinds of packing and covering (or alternatively, selection) problems, at least approximable.) Many of these can be solved both by problem-specific combinatorial algorithms and by LP. Indeed, some of their standard algorithms can be interpreted as applications of the the primal-dual method for solving LPs; moreover, the various max-min (in)equalities turn out to be special cases of LP duality.

Instructor: Prof. Matthew P. Johnson
email: mpjohnson@gmail.com

Office hours: By appointment. Office: 4327. This semester I'll be at the Graduate Center most Thursdays and Fridays, some Mondays and Tuesdays, and very few Wednesdays.

I want the course to run smoothly, enjoyably and profitably. Feel free to let me know what you find good, interesting and fun about the course. Let me know sooner about the opposite.