-

Euler Institute for Discrete Mathematics\\ and its Applications\\ ANNUAL REPORT 2000

Euler Institute for Discrete Mathematics
and its Applications
ANNUAL REPORT 2000

    

Preface

The most important event for the research school EIDMA was the formal recognition for a second period of five years by the KNAW. News about this reached us on June 27, 2000. From the official report we quote

"The subcommittee observes with pleasure that EIDMA also has obtained an international reputation by now".and "The subcommittee has a positive impression of the educational program."
This is the right place to thank the people involved in the preparation of our renewal application. Representatives of all the participating groups were asked to supply all sorts of information additional to what already can be found in the annual reports. A delegation of graduate students had to meet the committee in Amsterdam (some of them had to come from far away). A group of three "wise men" put a lot of thoughts in the self-evaluation and in the program for the next five years. Feedback from the participating groups was essential in this process. Thanks to all of you.
Sixteen of EIDMA's graduate students received a Ph.D. degree in 2000. As before, they have profited from EIDMA's graduate program that our own members carry for a major part.
EIDMA was fortunate to have found the following distinguished and eloquent scholars willing to teach a minicourse to her members:

A final thing that is worth to be mentioned here is that a second member of EIDMA became Fellow of the IEEE.
Let us continue our good cooperation. Together we carry EIDMA and that is our strength.

Prof.dr.ir. H.C.A. van Tilborg
Scientific Director EIDMA

    

1  Structure and Composition of EIDMA

1.1  Organizational Structure

1.2  Participating Groups

In 2000, EIDMA consisted of the following groups and persons:

2  EIDMA courses, seminars and meetings in 2000

In 2000, EIDMA organized the following courses, seminars and meetings:

3  Research Activities

The research activities of EIDMA concentrate on three main topics:

We first give a short description of these three areas of research and then, in the subsequent sections, list the contributions of the various research groups in these areas.

Discrete algebra and geometry

Design theory
Existence results, constructions and possible unicity of finite discrete structures with a given specification (often by means of some parameters). The structures can be classical block designs, but also association schemes, mutually orthogonal Latin squares, etc.

Geometry
The study of the geometry of groups of Lie type, buildings (introduced by Tits) and the diagram geometries of Buekenhout. Constructions, characterizations and classification problems of incidence geometries such as generalized polygons, near polygons, (semi)partial geometries are part of the research activities. Also included are combinatorial problems concerning point sets in finite projective planes and spaces, especially blocking sets and arcs as well as characterizations of quadric and Hermitian Veronese varieties.

Algebra
The classical relation between algebra and geometry enables the use of algebra to solve geometric problems. In particular need to be mentioned linear algebra, group theory, Clifford algebras and, to a lesser degree, number theory and topology.

Computer-algebraic methods
Algebra viewed as the study of operations on sets can, when the computer is able to perform these operations, be supported by expert systems, formula-manipulation, searching software, as well as classical computations. The study of the methods to realize this is the focus of this project.

Coding theory, information theory and cryptology

Source coding
Determining the most efficient (shortest) way to represent a certain amount of information. Designing algorithms that realize such a representation.

Channel coding
Representing an amount of information, that makes reliable transmission possible. Designing algorithms, that realize reliable transmission.

Coding methods for communication networks
The study of source and channel coding, encoding and addressing (protocols) in networks.

Cryptology
Protecting information against unauthorized access (privacy), determining if a message has been altered by a third party (integrity), adding a signature to an electronic document and verifying the identity, all by mathematical means.

Combinatorial optimization, combinatorial algorithms and graph theory

Algorithms for NP-hard problems
The development and analysis of optimal and suboptimal algorithms for NP-hard problems.

Polynomial algorithms, combinatorics and graph theory
The design and analysis of optimization algorithms that have a polynomial-bounded complexity. The application of these algorithms.

Graph-theoretic problems
Graph theory deals with a variety of different problems. We mention functions that transform graphs into graphs like line graphs, topics like perfect graphs, cycle coverings of graphs and homomorphisms of graphs, the relation between graphs and cooperative games, and graph theoretic applications in knowledge-technology and social sciences.

A different area concerns the representation of graphs, metric graph theory (with emphasis on shortest paths), the relation between geometric and algebraic structures, applications in discrete location theory and the theory of (dynamic) searching in graphs.

Cycles and paths in graphs
The existence of Hamilton cycles in graphs and, more general, of cycles and paths with particular properties.

3.1  Discrete Algebra and Geometry

3.1.1  Technische Universiteit Eindhoven,
Faculteit Wiskunde en Informatica, Sectie Discrete Wiskunde

3.1.2  Centrum voor Wiskunde en Informatica, Amsterdam

Disjoint paths and cycles.
A. Schrijver found a new, short proof of Mader's theorem on the maximum number of vertex-disjoint S-paths (to appear in Journal of Combinatorial Theory, Series B).
Together with A. Caprara and A. Panconesi, R. Rizzi extended on their previous work on the approximability and nonapproximability of the cycle packing problem. This work was meant to serve as a completion on previous work on the approximability and nonapproximability of the cut packing problem by A. Caprara and A. Panconesi and R. Rizzi.
With A. Sebo, A.M.H. Gerards continued the earlier project on min-max relations for packing circuit with prescribed homologies on Klein's bottle (an their interelations). A report is under preparation.

Lift-and-project methods for integer programming.
M. Laurent has studied how a lift-and-project method introduced by Lovász and Schrijver (1991) applies to the max-cut problem. She shows that if a graph has k edges whose contraction produces a graph with no K5 minor, then its cut polytope can be found after k iterations of the basic N operator applied to the metric polytope of the graph. Thus n-4 iterations suffice for a graph on n nodes and m edges, instead of the bound m provided by the general theory. Under some connectivity assumption, the bound becomes n-a(G)-3, thus giving an analogue of the Lovász-Schrijver result for the maximum stable set problem in the more general context of max-cut.

Matroids.
With J. Geelen (Waterloo, Canada) and G. Whittle (Wellington, New Zealand), A.M.H. Gerards continued working on matroids with bounded branch-width. A report has been prepared and will appear in Journal of Combinatorial Theory, Series B. Consequences for the graphic case have been develloped and included into the report.
With J.Geelen, A.M.H. Gerards worked on a forbidden minor characterization for pairs of regular matroids with a "Pfaffian orientation", generalizing a theorem of Little. It turned out that the orientations do not have the uniqueness properties one would hope for in proving such a result. It is unlikely that this research will be continued.
With J. Geelen, A.M.H. Gerards worked on a decomposition theorem for binary matroids with no K5-minor; partial succes has been acchieved when also K3,3-minors are excluded. The research probably will be continued.

Stable sets.
With M. Conforti, A.M.H. Gerards worked on a general decomposition theorem for the stable set problem. This as spin-off of their earlier project on stable sets in cap-free graphs with no even holes. A report on the entire project is under preparation.

3.1.3  Technische Universiteit Delft,
Faculteit Technische Wiskunde en Informatica

The 3-class assocation schemes connected with checkered hadamard matrices of order 16 have been been classified. Multilinear representations of matroids have been investigated.

3.1.4  Katholieke Universiteit Brabant,
Faculteit der Economische Wetenschappen

3.1.5  Université Libre de Bruxelles,
Département de Mathématique

3.1.6  Philips Research Labs., Eindhoven

3.1.7  Universiteit Gent,
Vakgroep Zuivere Wiskunde en Computeralgebra

3.2  Coding Theory, Information Theory and Cryptology

3.2.1  Technische Universiteit Eindhoven,
Faculteit Wiskunde en Informatica, Sectie Discrete Wiskunde

Coding theory

Linear codes over the integers modulo the square of a prime have been studied. In particular, generalizations of Kerdock and Preparata codes were defined and their structure was investigated.

The structure of order domains has been investigated.

The q-th power algorithm to get the normalization of a ring was generalized and applied to the problem of the missing functions.

The generation of pseudorandom sequences using linear recurrence relations over points of elliptic curves is being studied and particular pseudorandom properties have been shown.

Methods for polynomial factorization over finite fields based on 'implicit' linear algebra were studied. With a software implementation of such a method, a polynomial over the binary field of degree 1 million could be factored, using a single workstation. (joint work with P. Fleischmann and M. Holder).

A new associative block design has been constructed. Special subsets of codes and designs were investigated in cooperation with C. Godsil, W. Martin, and J.H. Kolen.

Cryptology

A textbook on cryptography has appeared. Its electronic version is a Mathematica notebook, which makes it possible for students to run and change all examples.

A general protocol combining Advantage Distillation and Information Reconciliation is developed, with as the aim reducing information leakage to the adversary.

Verifiable secret sharing (VSS) schemes deal with the problem of cheating dealers and cheating participant by detecting cheating. Publicly verifiable secret sharing (PVSS) schemes are a refinement of VSS schemes which also enables outsiders (rather than just the participants) to detect cheating. A simple and Efficient PVSS scheme has been constructed.

A probabilistic upper bound on the adversary's knowledge during a quantum transmission is derived.

The performance of authentication codes is studied for the situation that the encoding rule is only partially secret. We show how the legitimate users can use an authentication code in privacy amplification to thwart active attacks.

Differential and linear distributions of substitution boxes for symmetric-key cryptosystems have been studied. In particular, all possible distributions were determined for permutations on four bits, which is an important case for practical applications. In addition, theoretical connections between the distributions were studied.

Certain group signatures with added functionality were investigated.

PVSS (see secret sharing schemes) has been applied in electronic voting protocols. Auxiliary protocols for electronic voting have been developed such as a protocol for proving in zero-knowledge that a committed value is contained in a given interval, without revealing any additional information on the committed value.

An alternative setting for discrete logarithm based cryptosystems is developed, that can be used for, e.g., Diffie Hellman key agreement, ElGamal encryption and Nyberg-Ruepel signatures. The system, that is called XTR, is based on a field extension of degree 6. The two main advantages of XTR are its efficiency and its compactness. For instance, the number of bits that need to be exchanged for Diffie Hellman key agreement is one third of what is used in the standard DH scheme, while the offered security against attacks known today is equal to the one offered by the standard DH scheme.

At a later stage several improvements to the original XTR are described. This ranges from faster key generation and membership testing to faster exponentiation routines. As a consequence, signature applications are twice as fast and key agreement protocols and encryption/decryption algorithms are sped up as well.

The security of Lenstra's variant of DSA without long inversions has been analyzed. This variant is fully compatible with standard DSA signatures, but uses a different, but faster, algorithm to obtain them. Theoretical lower bounds for the security of the variant are given.

A bug in PGP concerning key revocation keys was found. This allows a malicious user to revoke the key of an ignorant and unrelated user. If applied at a large scale, this would constitute a denial-of-service attack.

3.2.2  Philips Research Labs., Eindhoven

3.2.3  KPN research Lab., Leidschendam

3.2.4  Technische Universiteit Eindhoven,
Faculteit Electrotechniek

Source and Channel Coding
Programme members: dr.ir.Tj.J. Tjalkens, dr.ir. F.M.J. Willems, dr. V.B. Balakirsky, prof.dr.ir. P. Schalkwijk (guest).

Programme design in brief
Sub-mission: In a communication system information is either transmitted or stored. Information and Communication Theory is concerned with fundamental limits in transmission and storage. The first objective in this area is to establish such limits; the second is to develop efficient methods that approach these limits as closely as possible. These methods often use coding, i.e. representing data in some other form.

Source coding is concerned with removing redundancy from data such that the original data can be exactly reproduced from the encoded data (noiseless source coding, compaction), or with removing irrelevancy from the original in which case some distortion between the reproduction and the original data is introduced (lossy coding, compression). In both the noiseless and the lossy case our research objective is to find techniques (codes) that are universal, i.e. achieve a high compaction or compression without knowing the source statistics in advance, and that have a low implementation cost. Channel coding involves adding redundancy to data that are to be transmitted over a channel. This is done in such a way that possible channel-errors can be corrected. While in the past researchers concentrated on finding the best error-correcting codes for relatively simple channels, the objective is now to find codes that allow efficient decoding procedures, often for channels with a more complex structure.

Overview of scientific results

Source Coding
In its first year, the Ph.D. project "CTW applications" was mainly devoted to literature study (CTW, dictionary methods, etc.). A first research problem that was addressed was to find compaction techniques for sources that satisfy a so-called permutation property. This property implies that all the contexts with a certain composition have the same parameter. Universal coding methods were proposed for these sources and their redundancy behaviour of was studied.

The investigation into the trade-off of computational and storage complexity versus redundancy in optimal source codes resulted in a new understanding and analysis of enumerative methods for Huffman codes. These results complement perfectly the results obtained the year before for the variable-to-fixed length optimal codes (Tunstall codes). We now have a nicely symmetric picture of this trade-off for the two optimal codes.

Our text compaction algorithms use symbol-decomposition to split ASCII characters into binary symbols. The context-tree weighting (CTW) algorithm compresses these binary symbols more or less independently. This results in model redundancy for the models of all these symbols. In 2000 a method was developed that tries to combine the descriptions of all these models in order to save redundancy. This method is again based on weighting. So far only very small improvements in compaction rate could be obtained with this new technique.

Model-estimation based in context-tree maximizing was studied again. Convergence of the estimator could be shown for sources with a tree structure. Moreover some suboptimal maximizing methods were proposed and their performance was discussed. The results of this study appeared in the proceedings of the CISS2000.

Channel Coding
A method is considered that is a competitor to existing computer arithmetic. We describe an encoding procedure that allows us to represent integers by binary vectors (codewords) in such a way that addition is replaced by the OR operation applied to these vectors. The sum can be reconstructed using the decoding algorithm. As a result, many of the transformations can be realized using parallel processing.

A class of binary codes is constructed that can be effectively used for asynchronous data transmission. The codes are defined for any odd code length by a regular algorithm, which is based on properties of regular, ordered, oriented, rooted, binary trees. We have addressed implementation issues and could show that these codes can be used in such a way that encoding and decoding complexities are linear functions of the code length.

We have developed a sequential decoding algorithm for low-density linear block codes for transmission over binary-input memoryless channels. The key point of our iterative approach is the representation of codewords as extremal points of the hypercube [0,1]n in Euclidean space. Here n is the codeword length. The vector of corresponding a-posteriori probabilities now replaces the received vector. This vector is corrected to a 0-1 vector using a sequential decoding technique. The performance of the proposed algorithm is analysed.

A model for the embedding of information in a source sequence was investigated. This information is to be recovered from a noisy version of the sequence in which the information is embedded. We show that there is a balance between the information rate and the distortion that results from embedding. An upper bound on the achievable rate for a given distortion level is given. This problem turns out to be closely related to the Gelfand-Pinsker side-information problem.

The hardware implementation of a turbo decoder for high bit rates is challenging. This is partly due to the inherent decoding latency of the MAP-algorithm, which is the key building block of the decoder. Moreover, power consumption in the MAP-algorithm turns out to be a problem at high data rates. An analysis of power consumption in the MAP-algorithm showed a bottleneck in memory accesses. Therefore, the Data Transfer and Storage Exploration (DTSE) methodology, developed at IMEC, has been applied. As a result the required data rates for wireless communications could be realized and power consumption and latency was decreased.

A method was developed to construct lower rate codes from a known high rate convolutional code by inserting dummy bits into the information bit sequence before encoding. Like other multi-rate codes these codes can adjust the amount of protection given to the information bits, and can be decoded using the same decoder as for the mother code. Our analysis and simulation results shows that the proposed recursive systematic insertion convolutional codes achieve a performance which is comparable to that of the corresponding optimal recursive systematic repetition convolutional codes.

Programme development

Source coding
An investigation will start into the possibilities and performance penalties of implementing parallel encoders and decoders for context oriented data compression systems. The importance of this study lies in the fact that context oriented algorithms (e.g. PPM, CTW) compress very well but are complex and therefore slow methods. Their speed must be improved in order to compete well with the current standard (LZ algorithms).

A collaborative filtering method can recommend a product to a person by exploiting similarities between the person and other people whose purchases have been stored in a database. A Bayesian network describes the relation between data streams. In 2001 we will study the relation between collaborative filtering and Bayesian networks and data compaction methods.

Channel coding
We will continue our research on probabilistic decoding algorithms. The emphasis will be on parallelisation and decoding architectures. This research is performed in cooperation with Philips Research.

Co-operation with external organisations:

3.2.5  Technische Universiteit Delft,
Faculteit Technische Wiskunde en Informatica

As for optimal linear codes the non-existence of several binary linear codes of dimension nine and of ternary and quaternary codes has been established. A new set of constraints for the weight distribution of general linear codes has been found. This promises to produce a major breakthrough in solving the problem of optimal linear codes over larger alphabets. Many polynomials haven been found for which the corresponding CRC codes perform better in comparison with existing standards, like IEEE and ATM. For spherical codes Boyvalenkov's method has been implemented in the program SCOD. This yielded quite a few upper bounds on the size of spherical codes. New methods have been found for the construction of self-dual codes over fields of size 2r and 3. Linear codes which are sandwiched between the binary Reed-Muller codes R(1,2k+1) and R(1,2k) have been studied in the framework of multilinear algebra. Polynomial invariants of the general linear groups GL(m,2) are useful in the classification of binary [n,m]-codes. For the case m = 3 a list of 10 invariants has been constructed which is complete in the sense that two [n,3]-codes are equivalent if and only if each of the 10 invariants has the same value on both codes. The research of the snake-in-the-box codes ( < 2,n > -codes) was continued. Another new non-asymptotic bound was established by counting claws adjacent to the snake. A construction for optimal coverings of certain hypercubes with symmetric snakes was developed. Furthermore, the Ph.D. thesis of Lukito on this subject was completed.

3.2.6  Nationaal Bureau voor Verbindingsbeveiliging, Den Haag

Research activities:

3.2.7  Katholieke Universiteit Leuven,
Departement Elektrotechniek-ESAT

The goal of COSIC's research activities is to create an electronic equivalent for primitives in the physical world such as confidentiality, signatures, identification, anonymity, notarization, and payments. To achieve this goal, the research concentrates on the design, evaluation, and implementation of cryptographic algorithms and protocols, and on the development of security architectures for computer systems and telecommunications networks.
COSIC's theoretical work on cryptographic algorithms and protocols is mainly based on discrete mathematics (a.o. number theory, finite fields, Boolean functions, finite geometry, and coding theory); other fields of mathematics relevant to our research include statistics and optimization. The goal is to achieve efficient and (provably) secure solutions. COSIC intends to integrate these solutions into different applications including computer systems, telecommunications systems (Internet security, mobile communications), and payment systems. Important aspect here are the efficient implementation (in both software and hardware) of cryptographic primitives and the security evaluation of components and systems including smart cards. COSIC provides consultancy in the area of computer security and cryptography.

COSIC collaborates closely with the company Utimaco Belgium.

COSIC cooperates with Ecole Normale Supérieure, ICRI, Royal Holloway University of London, Technion - Israel Institute of Technology, Technische Universiteit Eindhoven, Université Catholique de Louvain, University of Bergen, University of California at Los Angeles, University of Klagenfurt, and Queensland University of Technology.

COSIC also cooperates with Banksys, British Telecom, EEMA - The European Forum for Electronic Business, Europay International, Imec, Matra, Nokia, Philips, PricewaterhouseCoopers, Proton World International, RSA Laboratories, Siemens AG, SmartMove, LCI SMARTpen, S.W.I.F.T., the Dutch organization for Applied Scientific Research (TNO), and Ubizen.

Some important projects are:


COSIC's current research and project information, publication list, and recent papers are available at http://www.esat.kuleuven.ac.be/cosic/.

3.2.8  Universität Gesamthochschule Essen,
Institut für experimentelle Mathematik


References:

  1. A.J. Han Vinck, "Coded Modulation for Power Line Communications," AE Journal, 2000, pp. 45-49, Jan 2000.
  2. M.H.N. Costa, "Writing on Dirty Paper," IEEE Tr. Information Theory, pp. 439-441, May 1983.
  3. P. Moulin and J. A. O'Sullivan, Ïnformation-theoretic analysis of information hiding," Preprint, available at http://www.ifp.uiuc.edu/ moulin/paper.html, 1999.
  4. W.H. Kautz und R.C. Singleton, "Nonrandom Binary Superimposed Codes," IEEE Tr. On Information Theory, 1964, pp. 363-377.
  5. S. Bitan and T. Etzion, "Construction for Optimal Constant Weight Cyclically Permutable Codes and Difference Families," IEEE Trans. on Information Theory, vol. 41, pp. 77-87, Jan 1995.
  6. Peter Frankl and Mikhail Deza, Ön the number of permutations with given maximal or minimal distance," Journal of Combinatorial Theory, 352-260, 1977.
  7. A.J. Han Vinck and Samuel Martirossian, Ön Superimposed Codes," in Numbers, Information and Complexity, Kluwer Academic Publisher, pp. 325-331.
  8. Samwel Martirosyan and A.J. Han Vinck, Ön Optical Orthogonal Codes with Correlation 1," 22 Symposium on Infoprmation and Communication Theory in the Benelux, May 15-16, Enschede, the Netherlands, ISBN 90-365-1598-X, pp. 53-57. Also Submitted to IEICE, Japan.
  9. Ön Permutation Codes," A.J. Han Vinck, 6th Int. Symp. On Communication Theory and Applications, 15-20 July, 2001, Ambleside, UK, ISBN 0-9540814-0-4, pp. 491-495.
  10. ] A.J. Han Vinck and Jeroen Keuning, Ön the Capacity of the Asynchronous T-User M-frequency noislesss Multiple Access Channel," IEEE Trans. on Information Theory, pp. 2235-2238, November 1996.

3.3  Combinatorial Optimization, Combinatorial Algorithms and Graph Theory

3.3.1  Technische Universiteit Eindhoven,
Faculteit Wiskunde en Informatica, Sectie Besliskunde en Stochastiek

Combinatorial Optimization

a. Semidefinite relaxations
Within the research project with Delft, Rotterdam and Utrecht, performance of approximation algorithms for a graph optimization problem based on a semi definite relaxation has been tested empirically against various local search methods.

b. Local search
Results were obtained in performance guarantees for local search methods for some scheduling problems. Also the complexity of the local search strategies has been studied.

c. Routing problems
Together with the research school BETA, a project on routing problems is executed. Big progress has been made in the construction of the computational complexity map of a whole class of routing problems. The progress was greatly thanks to Jiri Sgall from the Academy of Sciences and the Charles University in Prague, who was a visitor to our department for four months during the spring.

d. On-line optimization
On the field of on-line routing a start has been made with studying latency objectives. The competitiveness of an on-line bin-colouring problem has been settled. This has been joined work with Sven Krumke and Joerg Rambau from the Konrad-Zuse Zentrum in Berlin.

e. Scheduling problems
A more than 20 years standing problem on complexity of a scheduling problem on unrelated machines has been resolved by showing that this problem is NP-Complete.

f. Preprocessing
The effect of preprocessing on computing time and approximability of combinatorial optimization problems has been studied. It has been shown that preprocessing will not help to improve either of the two in most cases. A coincise view on these sort of techniques has been obtained, though a quite negative one.

g. Graph theory and network optimization
We investigated the complexity of recognizing whether a given directed graph is a subgraph of a de Bruin graph, and found it to be NP-complete. This problem is related to genomics, in particular the problem of sequencing given DNA fragments.

3.3.2  Université Libre de Bruxelles

Service d' Optimisation

3.3.3  Centrum voor Wiskunde en Informatica, Amsterdam

Disjoint paths and cycles.
A. Schrijver found a new, short proof of Mader's theorem on the maximum number of vertex-disjoint S-paths (to appear in Journal of Combinatorial Theory, Series B).
Together with A. Caprara and A. Panconesi, R. Rizzi extended on their previous work on the approximability and nonapproximability of the cycle packing problem. This work was meant to serve as a completion on previous work on the approximability and nonapproximability of the cut packing problem by A. Caprara and A. Panconesi and R. Rizzi.
With A. Sebo, A.M.H. Gerards continued the earlier project on min-max relations for packing circuit with prescribed homologies on Klein's bottle (an their interelations). A report is under preparation.

Lift-and-project methods for integer programming.
M. Laurent has studied how a lift-and-project method introduced by Lovász and Schrijver (1991) applies to the max-cut problem. She shows that if a graph has k edges whose contraction produces a graph with no K5 minor, then its cut polytope can be found after k iterations of the basic N operator applied to the metric polytope of the graph. Thus n-4 iterations suffice for a graph on n nodes and m edges, instead of the bound m provided by the general theory. Under some connectivity assumption, the bound becomes n-a(G)-3, thus giving an analogue of the Lovász-Schrijver result for the maximum stable set problem in the more general context of max-cut.

Matroids.
With J. Geelen (Waterloo, Canada) and G. Whittle (Wellington, New Zealand), A.M.H. Gerards continued working on matroids with bounded branch-width. A report has been prepared and will appear in Journal of Combinatorial Theory, Series B. Consequences for the graphic case have been develloped and included into the report.
With J.Geelen, A.M.H. Gerards worked on a forbidden minor characterization for pairs of regular matroids with a "Pfaffian orientation", generalizing a theorem of Little. It turned out that the orientations do not have the uniqueness properties one would hope for in proving such a result. It is unlikely that this research will be continued.
With J. Geelen, A.M.H. Gerards worked on a decomposition theorem for binary matroids with no K5-minor; partial succes has been acchieved when also K3,3-minors are excluded. The research probably will be continued.

Stable sets.
With M. Conforti, A.M.H. Gerards worked on a general decomposition theorem for the stable set problem. This as spin-off of their earlier project on stable sets in cap-free graphs with no even holes. A report on the entire project is under preparation.

3.3.4  Universiteit Twente,
Faculteit der Toegepaste Wiskunde

Graph theoretic problems
Graph theory deals with a variety of different problems. Topics studied in Twente at the moment are: cycles in graphs, independence trees, flows in graphs, graph classes and computational complexity, graph coloring , cyclic graphs etc., graph-theoretic applications in information technology, telematics, knowledge technology and logistics, especially concerning routing, capacity planning, and survivability of communication networks.

Hamiltonian graph theory
The search for conditions for the existence of Hamilton cycles, long cycles and cycles through prescribed vertex and/or edge sets in graphs, sometimes within special classes of graphs such as regular, claw-free or triangle-free graphs, graphs with a certain toughness.

Graph Theory
The Discrete Mathematics group has merged with the Operations Research group into the chair of Discrete Mathematics and Mathematical Programming. Prof. dr. C. Hoede retired in September 2000. The new chair will be taken up by Prof. dr. G.J. Woeginger from Graz in April 2001. An additional Assistant Professor will be solicited in order to strenghten the Graph Theory branch within the new chair. He or she is expected to join the group before summer 2001. The main focus of the research within the new chair will be on fundamental mathematical research related to the application areas telecommunication and logistics.

Game Theory
T.S.H. Driessen continued his study of several problems in cooperative game theory.

Application of Graph Theory
The group intends to further explore applications in Information Technology and Telematics.

3.3.5  Philips Research Labs., Eindhoven

3.3.6  Rijksuniversiteit Groningen, Quantitative Logistics Research Group

Diptesh Ghosh joined as a postdoctoral researcher in the Department of Econometrics and Operations Research in January 2000. He has been working on sensitivity analysis of discrete optimization problems and on aspects of the simple plant location problem. He published six SOM research reports, attended and presented a paper in the XXXIII Annual Convention of the Operational Research Society of India, and presented two seminars, one for QLORG on October 25, 2000 and one at the Indian Institute of Management Ahmedabad on December 22, 2000.

Boris Goldengorin has introduced equivalent instances for the Simple Plant Location (SPLP), i.e. instances that each feasible solution to the SPLP has the same goal function value and they are differ at least on two elements for any pair of distinct instances. Together with D. Ghosh and G. Sierksma he defined a collection of polytopes whose union describes the set of instances equivalent to a given instance. He uses the concept of equivalence to extend the set of instances that can be solved by using the available knowledge of polynomially solvable special cases for the SPLP. Based on the LP approach and the concept of equivalence he has found a new algorithm that allows to determine sites in which facilities will be located in an optimal solution and thereby reduce the size of a problem instance.

Caspar Schweigman executed and supervised research in the field of food security in Africa. Stochastic programming models were developed (together with Maatman, Ruijs and van de Vlerk) to study farmers' strategies as a response to uncertain rainfall patterns in Burkina Faso. Spatial equilibrium models were developed for cereal markets in developing countries, with specifically handling the stochastic nature of prices (toghether with Ruijs and Lutz). He was much involved in the interuniversity collaboration with the School of Economics and Business Administration of the University of Can Tho in Vietnam, and with the Economics Faculty of the University of Ouagadougou in Burkina Faso. As a Director of the Centre for Development studies of the University of Groningen he helped to start up in Groningen a Masters Programme on Humanitarian Assistance.
Gerard Sierksma became a professor of logistical management at the department of marketing and marketing research of the faculty of economic sciences on August the first. He attended and presented papers at the Nationale Wiskunde Dagen (February), the Grünbaum-Klee Symposium in Israel (April), OR2000 Symposium Milan (September), and at the Coach Platform Meeting Papendal (December). This last event was a result of the media attention, during the European football championships, obtained with his program the Computer Coach with which simulations were executed concerning the Dutch-eleven line up. Since then the program is redesigned as a decision support tool for scouting and head-hunting purposes.

Gert Tijssen continued research in the field of linear optimization (duality between multiplicity and degeneracy, Balinski- Tucker tableaus and their applications), data-correcting algorithms for the simple plant location problem, and efficient algorithms for finding the shortest paths in END/OR-graphs. Furthermore, he is working on computer programs for solving cutting stock problems in Dutch cardboard mills.

Maarten H. van der Vlerk continued research in the field of stochastic integer programming awarded from Dutch Royal Academy of Sciences.

4  Publications in 2000

4.1  Books

4.2  Research Articles

4.3  Conference Proceedings

4.4  Preprints and Internal Reports

4.5  Patents

5  Lectures in 2000

6  External Grants in 2000

7  Noteworthy Activities in 2000

7.1  Awards

7.2  Ph.D. Degrees

7.3  Ph.D. Committees

7.4  Editorship

7.5  Organisation of workshops and conferences

7.6  Memberships