# Combinatorial Algorithms

Combinatorial Algorithms
Spring 2015
Prof. Matthew P. Johnson
“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)

Prerequisites: Algorithms, and mathematical maturity; also, basic knowledge of discrete math and linear algebra.

Texts: A Course in Combinatorial Optimization (Schrijver; http://homepages.cwi.nl/~lex/files/dict.pdf) and Combinatorial Optimization: Algorithms and Complexity (Papadimitriou &
Steiglitz)

Assessment: Biweekly problem sets, and a project (survey paper or implementation).

Course summary: This is a course on combinatorial algorithms (or, as some would say, algorithms), covering topics (far) 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 graphs. In such problems, we search a finite but typically exponentially large set of valid solutions—e.g., all matchings in a graph—for one maximizing or minimizing some objective function. Nonetheless, most of the problems we study in this course are optimally solvable in polynomial time. The fundamental topics here are matchings, flows and cuts, shortest paths and spanning trees, and matroids. An overarching theme is that many such problems have traditionally been studied both a) by computer scientists, using discrete, combinatorial algorithms (greedy, DP, etc.), and b) in the operations research optimization community, where they are treated as continuous optimization problems (solved by LP, etc.). We will often compare the two approaches, and we will find that it can be fruitful to combine them. In particular, we will repeatedly use is linear programming throughout the course.

Rationale: Combinatorial algorithms is a core part of algorithms, which is a core part of computer science, as perhaps evidenced by the epigraph above (from the paper in which Edmonds gave his algorithm for maximum matching in general graphs). Many of the optimization problems that are most fundamental to computer science and have had the greatest “broader impact” outside of computer science and indeed within the wider world—shortest paths for travel, network flow for business and transportation, maximum matching for resource allocation, linear programming for myriad operations research problems—are among the topics covered in this course.

Learning goals: Learn some of the canonical algorithms (and algorithm schemata) for solving fundamental matching, flow, and path problems; become able to apply and extend these techniques to new problem variations; come to see how many of these problems are mutually reducible to one another; gain an appreciation of the conceptual foundations of duality and matroid theory, and of polyhedral combinatorics as mathematical technology.

Topics:
• shortest paths and spanning trees
– single-source (Dijkstra, Bellman-Ford)
– all-pairs (Floyd-Warshall)
– spanning trees (Prim, Kruskal)
– arborescences (Edmonds)
– NP-Complete extensions (CDS, Steiner, etc.)
• linear programming
– convex hulls and polyhedra
– simplex, etc.
– LP-rounding for approximation
– duality
– packing and covering LPs
– primal-dual method
– totally unimodular matrices
• convex optimization
– convex programming
– Lagrangian duality
– semi-definite programming
• matchings
– unweighted bipartite (augmenting paths)
– weighted bipartite (Hungarian)
– unweighted non-bipartite (Edmonds)
– weighted non-bipartite (more Edmonds)
– NP-Complete extensions (GAP, 3DM, etc.)
• network flows
– disjoint paths (Menger)
– max flow / min cut
– augmenting path algorithms
– push-relabel algorithms
– min-cost max flow
– multi-commodity flow and multicut• matroid theory
– matroid intersection
– matroid union
• optional side topics
– string matching (Rabin-Karp, KMP)
– online algorithms (paging, k-server, secretary)
– scheduling