US-France Cooperative Research: Analysis and Evaluation of Combinatorial Structures and Algorithms

North Carolina State University, Raleigh NC

Investigators

Abstract

0230800 Savage This three-year award for U.S.-France collaboration in applied mathematics involves Carla D. Savage, Pawel Hitczenko, and William Stewart of North Carolina State University and Sylvie Corteel and her team at the University of Versailles. The project focuses on an integrated approach to the analysis of combinatorial algorithms arising in applications. In many applications, there are problems whose solutions require examination of an exponential number of possibilities. The current heuristic approach to these problems requires much time. The investigators focus on an alternative approach that incorporates probabilistic modeling techniques for combinatorial problems. The problems are drawn from areas of computational biology, routing in optical networks, resource management in distributed and multiprocessor systems, and classical combinatorics. The objectives are twofold: (1) devise new methods to attack classical problems in combinatorics with probability and Markov chains; and (2) develop an integrated combinatorial/algorithmic/probabilistic approach to applied problems for which traditional methods from a single area have proved inadequate. This award represents the US side of a joint proposal to the NSF and the French National Center for Scientific Research (CNRS). NSF will cover travel funds and living expenses for the US investigators and graduate students. The CNRS will support the visits of the French researchers to the United States. US students will benefit from the exchange of scientific techniques and experience with an international research team.