ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

17. Control Theory and Optimization

1991 MS Classification: 05C85, 05C90, 90B06, 90B10, 90B35 Schrijver, Alexander, CWI, Amsterdam, and University of Amsterdam, The Netherlands Routing and timetabling by topological search

We discuss how decomposing the search space into homotopy classes can help in finding solutions to combinatorial optimization problems. Searching any homotopy class then amounts to finding a group function ψ on the arcs of a directed graph such that ψ is cohomologous to a given function ϕ and such that ψ has values in a prescribed range. We describe applications to two specific classes of NP-complete problems: routing wires on a chip (where the main tool is solving the cohomology problem in a free group, and a main result the polynomial-time solvability of the wire-routing problem for any fixed number of modules), and finding a periodic timetable (applied to the Dutch railway timetable, where liftings of the period group C_{60} to the integers give the classes to be searched). The methods also imply a characterization of the existence of an isotopy of a compact surface S that brings a given set of disjoint closed curve on S to a given undirected graph embedded on S.

ICM 1998 Berlin · Plenary and Invited Lectures