4.1. Discrete Mathematics and Optimization

Programme leaders: C. Roos, A. Schrijver

Aim of the programme
- The analysis of large and complex combinatorial structures (like networks) with mathematical methods (algebra, geometry, topology, graph theory).
- The design of efficient and robust (modelling and algorithmic) methods for optimization and decision problems, and testing and applying the results to problems from practice (logistics, distribution, transport, engineering).

Some results in the evaluation period:
- CWI and UvA
Research of the research groups in Amsterdam focused on geometric and topological methods and questions in discrete mathematics and optimization.
In particular, conjectures were proved of Kusner (1983) concerning the maximum number of equidistant points in the rectilinear space of dimension $d$ in the case $d\le 4$ (with J. Koolen), and of Robertson and Thomas on the orientable genus of a graph $G$ embedded in a nonorientable surface (with B. Mohar).
New polynomial techniques were found and applied in finite geometries, in particular to blocking sets, maximal arcs, semifields, and flocks (with S. Ball, M. Lavrauw, T. Sznyi, and L. Storme). It was shown that each graph is strongly t-perfect if each $K_4$-subdivision is t-perfect, and that corank 3 Colin de Verdiére matrices correspond to 3-dimensional vector flows (with L. Lovász).
Moreover, simple proofs were found for the finite convergence of the Lasserre hierarchy of semidefinite relaxations for 0/1 polytopes, of a theorem of Mader on disjoint $S$-paths, of a theorem of Guenin characterizing weakly bipartite graphs, and of Seymour's regular decomposition theorem (with J.F. Geelen).
Further research concerned branch-width, matroid minors, and well-quasi-ordering of matroids (with J.F. Geelen and G. Whittle), regular matroids with a Pfaffian orientation, decomposing binary matroids with no $K_5$-minor, packing circuits with prescribed homologies on Klein's bottle (with A. Seb), and decomposing weakly bipartite graphs and other graphs in relation to the stable sets (with M. Conforti), and the geometry of the set of moment matrices underlying the Lasserre relaxations for the maximum-cut problem.
- TUD
We introduced new (so-called self-regular) primal-dual barrier functions, which induce new search directions and hence new interior-point algorithms. We showed that large-update methods obtained in this way (for linear, second-order and semidefinite optimization) have better complexity bounds than known before. This was the subject of the PhD thesis of Peng; a research monograph based on these results will be published by Princeton Unversity Press.
New results concerning the limit point of the central path for semidefinite optimization were obtained.
Improved approximation results were obtained for the MAX-k-CUT problem, for $k > 2$. Also, improved complexity results were obtained for the problem of minimizing a quadratic function over the simplex (the so-called standard quadratic problem).
Novel theoretical and computational work was also done on the (maximum) satisfiability problem.
Robust variants of a quadratically constrained uncertain problem were proposed and analyzed (with Ben-Tal and Nemirovski).
Generalizations of the Lovasz-Schrijver (LS) proof systems were investigated, in connection with the problem of finding good lower and upper bounds on the original LS proof system. They turned out to be very strong, and allowed short proofs for the clique-coloring tautologies and other well-known "hard" instances.
The relevance of the so-called LS-ranks was analyzed, and connections with the well-known (generalized) Positivstellensatz established (with E.A.Hirsh and D.Grigoriev).
An SDP-based procedure for computing an efficient decomposition of a nonnegative bivariate polynomial into a sum of squares of rational functions was developed.
A problem of Nesterov on the complexity of the primal self-concordant barrier method was solved. A unification of necessary conditions for extremal problems was found. Joint work with V. Tikhomirov led to applications of the theory of convex cones on convex calculus and will lead to a monograph on optimization theory to be published by Princeton University Press. Work has been done on minimax theorems (with G.Kassay).

Prizes
The paper Robust versions of convex quadratic and conic-quadratic problems by Ben Tal, Nemiriovski and Roos received the ICOTA Best Theoretical Paper Award at the ICOTA 2001 meeting, Hong Kong, December 15-17, 2001 (ICOTA means: International Conference on Optimization. Theory and Applications).
J. Brinkhuis was in 2000 recipient of the Onderwijsprijs Erasmus University for excellence in teaching.