This award provides partial support for Professor Leslie E. Trotter to collaborate in mathematics with Professors Thomas M. Liebling and Dominique de Werra of the Department of Mathematics, Swiss Federal Institute of Technology, Lausanne. They share an interest in polyhedral combinatorics, and will collaborate on three specific lines of research in that general area. These current research topics are partially ordered sets, perfect graphs, and stability critical graphs. The Swiss research group is very active and has an excellent international reputation in the areas of combinatorial optimization and operations research. The lead Swiss collaborators have particularly notable research accomplishments on topics directly related to the proposed work. Professor Trotter is deeply involved in a substantial group effort at Cornell that will be significantly enhanced by collaboration with the group in Switzerland. Previous collaboration among these investigators was extremely productive. Polyhedral combinatorics is the study of the interplay between algebraic and geometric structure of polyhedra, on the one hand, and algorithmic aspects of linear objective optimization over polyhedra on the other. This approach has yielded effective optimization algorithms for computationally difficult models in broadly diverse fields such as inventory control, statistical mechanics, VLSI, econometrics and parallel machine scheduling. For example, the graph theory and algorithmic nature of stability critical graphs produce models with direct applications to forestry harvesting strategies and the allocation of computer memory.
