4.1. Discrete Mathematics
Programme leader: A.
Schrijver, A.J.J. Talman
Description of the programme.
Analyzing and optimizing large and complex combinatorial structures (like
networks) with mathematical methods (algebra, geometry, topology, graph theory),
designing efficient algorithms for optimization and decision problems, and
testing and applying the results to problems from practice (logistics,
We search for new methods and techniques to
analyze large and complex networks and to design optimal subsystems (like routes,
flows, or arcs). The research focuses on decomposing large networks by treewidth,
on visualizing them by 3D embeddings using new tools based on forbidden minors
and eigenvalue methods, on designing fast methods for routing problems in
networks on surfaces based on homotopy and groups, on developing new algorithms
for assignment, scheduling and timetabling using graphs, linear programming, and
branch-and-cut, and on testing and applying the new techniques to practice (like
at Dutch Rail).
We also focus on solving algorithmic problems with
geometric and algebraic methods.
Combining the classical tool of linear
programming with modern techniques like interior-point methods (Karmarkar), basis
reduction (Lenstra-Lenstra-Lovász), branch-and-cut,
semi-definite programming, and computer algebra (Gröbner bases), turns out
to be very powerful, both to estimate the complexity of combinatorial
and optimization problems, and to obtain efficient and practical algorithms to
solve them. The full power of these methods is still to be uncovered, but seems
potentially very high.
Part of this programme is devoted to the recent
interest in interior-point methods for linear and non-linear optimization. After
the succesful polynomial-time methods of this type for linear optimization the
research now focuses on polynomial-time methods for semi-definite and other
cone-optimization problems and randomized approximation schemes for non-convex
optimization problems. Besides this also multi-criteria decision analysis and
multi-objective optimization is a field of interest.