Programme leaders: C. Roos, A. Schrijver
The aim of the programme is the analysis of large and complex combinatorial structures (like networks) with mathematical methods (algebra, geometry, topology, graph theory), the design of efficient algorithms 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
Among the results achieved at CWI and the University of Amsterdam are the proof that the null space of any corank-3 Colin de Verdière matrix belonging to a 3-connected planar graph, gives a proper embedding of the graph in the plane (with L. Lovász), an uncrossing algorithm for set-pairs, a proof that the concepts of pairwise adjacency and of strong base orderability are equivalent for binary matroids, a new proof for Seymour's characterization of regular matroids that are neither graphic, nor co-graphic, a new, combinatorial algorithm to find the minimum value of a submodular function, the theorem that the class matroids representable over a fixed field and with bounded branch width is well-quasi-ordered under taking minors, an extension of the stable matching theorem of Gale and Shapley to partially orders and matroids, and a polynomial time algorithm for the stable set problem in cap-free graphs without even holes.
TUD and EUR
The research in the field of optimization anticipated on the recent interest in semidefinite optimization (SDO).
In this connection a number of interesting results have been obtained: several new algorithms were proposed and proved to be polynomial;
any SDO problem can be embedded in in a self-dual SDO problem satisfying the interior-point condition;
the NP-complete problem of minimizing a quadratic form over the intersection of commonly centered ellipsoids can be approximately solved in polynomial time;
new heuristics for the satisfiabilty problem were derived from semidefinite relaxations.
Further, several variants of the criss-cross method for linear and hyperbolic programming were shown to be finite, some smoothing methods for variational inequalities and nonlinear complementarity problems were proposed and an interesting new property of orthogonal matrices was shown to be equivalent with the Farkas' lemma.
For MCDA, this was a period of consolidation. Three popular MCDA methods were redesigned: two pairwise-comparison methods, the Additive AHP (AAHP) and the Multiplicative AHP (MAHP), and a direct-rating method (SMART). A logarithmic relationship was established between the AAHP and SMART on the one hand, and the MAHP on the other, using the observation that human beings express their preferential judgement by estimating ratios of subjective values or differences of the corresponding logarithms, the so-called grades. Hence, the arithmetic operations in the AAHP and SMART (arithmetic scales and means) are parallelled by the operations in the MAHP (geometric scales and means). Several test cases in energy planning, environmental assessment, health care, and university administration are documented in a monograph.
The participant Shuzong Zhang (EUR) received the 1999 prize for the best researcher of Erasmus University. Jiming Peng was one of the three finalists for the best student paper at the Hong Kong meeting on Nonlinear Programming and Varitional Inequalities.