CSc 80030: Combinatorial Algorithms
The Graduate Center, CUNY
Spring 2015
Th 6:30pm-8:30pm
Room 4419
There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially
with the size of the graph. It is by no means obvious whether or not there exists an algorithm
whose difficulty increases only algebraically with the size of the graph. ... It may be that since
one is customarily concerned with existence, convergence, finiteness, and so forth, one is not
inclined to take seriously the question of the existence of a better-than-finite algorithm.
— Jack Edmonds, “Paths, Trees, and Flowers” (1965)
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.
We won't follow a textbook as such, but rather will use portions of lecture notes and texts,
probably all of which are available free online. (Ask me if you need help.)
For most classes there will probably be preparatory reading to do in advance.
2/3 - problem sets (~5)
1/3 - project
The project can
take the form of either an expository paper, a nontrivial implementation project, or
(ideally) performing original research on a problem, which may be done in pairs; it will
also include a class presentation.
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.
- PS 3
- PS 2
- PS 1
- (1/29) intro: combin opt, spanning trees (and extensions: Steiner tree and CDS)
- (2/5) network flows, max flow - min cut
reading: ?
(2/12) no class: Lincoln's birthday
- (2/19) min-cost flows; extensions: multi-commodity flow and multicut
reading: ?
- (2/26) LP: convex sets, polyhedra, basic solutions
reading: ?
- (3/5) LP duality: intuition, dual prices, weak and strong, slackness, minimax theorem
reading: ?
- (3/12) algorithms to solve LPs: simplex, ellipsoid
reading: ?
- (3/19) LP: primal-dual method, auction algorithm, TU matrices
reading: ?
- (3/26) shortest paths: single-source (with dual, and Konig's theorem), all-pairs
reading: ?
- (4/2) matchings: unweighted bipartite, assignment problem, weighted non-bipartite (Edmonds); extensions: GAP and 3DM
reading: ?
(4/9) no class: spring break
- (4/16) more matching
reading: ?
- (4/23) submodular functions and optimization: min, max
reading: ?
- (4/30) Lagrangian duality
reading: ?
- (5/7) semi-definite programming
reading: ?
- (5/14) project presentations
mpjohnson@gmail.com
|