This project focuses on the design of approximation algorithms for NP-hard problems arising in two important application areas: (1) design of networks and (2) computational molecular biology. The work involves the development of general techniques to solve classes of problems in both areas, applying and extending tools from the area of approximation algorithms, such as the primal- dual schema, bicriteria formulations and approximations, and using graph-theoretic arguments in the proof of performance guarantee. In particular, the issues addressed in the area of network design include improved algorithm for minimum-cost survivable network design by extending the primal-dual method, and a generalization of the Steiner tree problem with covering requirements. In the area of computational molecular biology, the areas of investigation include the application of bicriteria approximation methods to the physical map assembly problem, and fundamental questions in multiple sequence alignments -- local, global and tree based. The Integrated Educational Plan of this CAREER Grant includes (a) participating as Resident Scientist in the DIMACS High School Teacher Education Program in Computational Biology, (b) developing a``more modern'' undergraduate cross-disciplinary computational biology at CMU, (c) establishing and running a graduate research seminar for doctoral students in the Algorithms, Combinatorics and Optimization Doctoral Program at CMU, and (d) developing new graduate courses in network design and approximation algorithms.***
