2003 Fulkerson Prize Citation

J. F. Geelen, A. M. H. Gerards, A. Kapoor, "The Excluded Minors for GF(4)-Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247-299.

Matroid representation theory studies the question of when a matroid is representable by the columns of a matrix over some field. The matroids representable over GF(2) and GF(3) were characterized by their excluded minors in the 1950s and the 1970s respectively. Rota then conjectured that the matroids representable over any finite field GF(q) could be characterized in terms of a finite list of excluded minors. For more than twenty five years, progress on Rota's conjecture stalled. The proofs for GF(2) and GF(3) relied on the uniqueness properties of representations over these fields, properties that do not hold for other fields. Thus the result of Geelen, Gerards and Kapoor came as a big surprise. The paper of Geelen, Gerards and Kapoor gives an excluded minor characterization for matroids represented over GF(4) by working around the non-uniqueness of the representation. It has reawakened interest in the area of matroid representation and brought renewed hope of progress towards the solution of Rota's conjecture.

B. Guenin, "A characterization of weakly bipartite graphs", Journal of Combinatorial Theory B 83 (2001), 112-168.

A long-standing area of interest in the field of discrete optimization is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. In the case of a particular set covering formulation for the maximum cut problem, a graph is called weakly bipartite if the polyhedron has integer vertices for that graph. Guenin's result gives a precise characterization of the graphs that are weakly bipartite in terms of an excluded minor. This solves the graphical case of a famous conjecture about ideal binary clutters made by Seymour in his 1977 Fulkerson Prize-winning paper. Guenin's proof makes an ingenious use of a deep theorem of Lehman, also itself a Fulkerson Prize winner. Guenin's work has motivated several remarkable subsequent papers.

S. Iwata, L. Fleischer, and S. Fujishige, "A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions", Journal of the ACM 48 (2001), 761-777, and
A. Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time", Journal of Combinatorial Theory B 80 (2000), 346-355.

Submodular functions provide a discrete analog of convex functions, and submodular function minimization arises in such diverse areas as dynamic and submodular flows, facility location problems, multiterminal source coding, and graph connectivity problems. The first polynomial-time algorithm for submodular function minimization was given by Grötschel, Lovász, and Schrijver in 1981; however, the algorithm relies on the ellipsoid method, requires advance knowledge of bounds on the function values, and is not combinatorial. In 1999, the papers of Iwata, Fleischer, and Fujishige, and of Schrijver independently gave combinatorial, strongly polynomial-time algorithms for this fundamental problem. These results are a significant step in the history of combinatorial, strongly polynomial-time algorithms for discrete optimization problems, and can be compared with the Edmonds-Karp algorithm for the maximum flow problem and Tardos's algorithm for the minimum-cost flow problem.