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
Stable sets. D.C. Gijswijt and A. Schrijver showed that the $b$-stable set polyhedron of graphs not containing a bad $K_4$-subdivision is determined by the edge and odd circuit inequalities.
Combinatorial Optimization - Polyhedra and Efficiency. A. Schrijver finished the book ``Combinatorial Optimization - Polyhedra and Efficiency'', which will appear in 2003 at Springer-Verlag.
Combinatorial Optimization - Semidefinite Relaxations. M. Laurent proved a linear lower bound for the number of iterations needed for representing the cut polytope of a complete graph as projection of semidefinite relaxations; she gave concise semidefinite representations for the polytopes whose vertices form a real variety associated to a radical zero-dimensional ideal, extending results of Lasserre in the grid case, and also proved combinatorial analogues of results of Curto and Fialkow about flat extensions of moment matrices, with applications to semidefinite representations of $0/1$ polytopes.
Binary matroids. J.F. Geelen (Canada), A.M.H. Gerards, and G. Whittle (New Zealand) continued their work towards a grid theorem for binary matroids. First they proved, in cooperation with N. Robertson (USA), a bound on the excluded minors for the matroids with branch-width $k$ (to appear in Journal on Combinatorial Theory, Series B) and a structural characterization for high branch-witdh in matroids representable over fixed finite fields (a report is almost finished). Later they proved that matroids that are representable over a fixed finite field have large grid-minors if they have huge branch-width. This provides (among other things) evidence for Rota's conjecture.
Polyhedral Combinatorics. A.M.H. Gerards, G. Maroti, and A. Schrijver derived very short and easy proofs for recently appeared results of Aguilera, Escalante, and Nasini, on the disjunctive index of relaxations of stable set polyedra.

- TUD and EUR
Barrier functions for convex cones. Jointly with A. Nemirovski and A. Ben-Tal (Technion, Haifa), Roos wrote a paper on a generalized matrix cube problem. A monograph (with Peng and Terlaky) on new, so-called self-regular barrier functions for primal-dual interior point methods was published by Princeton University Press. The research on this subject was continued and has led to some new and interesting barrier functions, some of them being not self-regular but nevertheless sharing all the good properties of self-regular barriers, and with improved complexity results when compared with the classical logarithmic barrier function.
Non-convex Quadratic Optimization, Semidefinite Optimization. E. de Klerk, D. Pasechnik (jointly with D. Grigoriev, IRMAR, Univ. Rennes I) proved a $n^{O(k)}$-upper bound for the complexity of $n$-variate quadratic optimization subject to $k$ (not necessarily convex) quadratic constraints. This bound in particular implies the sharpest known upper bound on the complexity of general semidefinite programming, claimed without a proof by L. Khachiyan and L. Porkolab in 1997. This result also shows that the so-called extended trust region subproblem is polynomially solvable (thus settling an open problem).
E. de Klerk, C. Roos (jointly with M. Halicka, Comenius Univiversity, Bratislava) gave a new characterization of the strict complementarity property for semidefinite programming in terms of the limiting behavior of the central path.
Convex Optimization. J. Brinkhuis worked on unification of necessary conditions (with Tikhomirov). A monograph on optimization theory based on these results will be finished in 2003 and published by Princeton University Press. The concept D-induced duality was developed (with Zhang).
Minimax results. J.B.G. Frenk was able to prove that some well known minimax results for infinite dimensional topological spaces using only finite dimensional separation. Moreover, a chain of well known minimax theorems starting with the famous minimax result of von Neumann published in 1928 were derived from each other using very elementary properties of compact sets and lower semi-continuous functions. Finally, some of these results were extended to the larger class of Borel probability measures by means of the Riesz representation theorem for the dual space of the set of continuous functions on a compact Haussdorff space, the Banach-Alaoglu theorem and the Fubini-Tonelli theorem.

- TUE
L. Stougie, in cooperation with others, obtained several results.
On-line routing. Together with S. Krumke, D. Poensgen and W. de Paepe, M. Lipmann, X. Lu and R. Sitters several results have been obtained. A first step to study on-line elevator systems has been made. Together with R. Sitters and W. de Paepe the CNN-conjecture has been proven. This is considered one of the most important open problems in on-line optimization.
Minimum test set. Together with K.M.J. de Bontridder, B. Haldersson, M. Haldersson, C.A.J. Hurkens, J.K.Lenstra, and R. Ravi, a problem important in medical diagnostics and biological identification has been studied. Both approximation results has been obtained and exact algorithms have been designed.
Randomized Algorithms and Counting. Together with M. Dyer and R. Kannan a work on fast randomized algorithms for convex optimization has been completed. Together with M. Dyer the complexity of stochastic programming problems has been studied. Together with M. Dyer, M. Cryan and H. Mueller vertices of transportation polytopes have been counted approximately using Markov Chain techniques.
Transportation polytopes. A first strongly polynomial bound on the diameter of the transportation polytope was derived. Together with J. van den Heuvel the cubic bound was improved to a quadratic bound, which was afterwards, together with Graham Brightwell, improved to a linear bound.

Prizes and awards
- On June 15, 2002, A. Schrijver received a honorary doctorate of mathematics from the University of Waterloo in Waterloo, Ontario.
- Jiming Peng received the Stieltjes price for the best mathematical thesis in 2001 of the Stieltjes Institute.
- H. van Maaren and M. Heule were awarded for developing the second best SAT-solver in the category on random benchmarks at the SAT-solver Competition 2002 at the 5th International Symposium on Theory and Applications of Satisfiability Testing, Cincinatti.