CAREER: Approximation algorithms for NP-hard problems in networks and biology

该项目的重点是在两个重要的应用领域中出现的NP难问题的近似算法的设计：（1）网络设计和（2）计算分子生物学。 这项工作涉及的一般技术的发展，以解决这两个领域的问题类，应用和扩展工具，从该地区的近似算法，如原始-对偶模式，bicriteria配方和近似，并使用图论参数的证明性能保证。特别是，在网络设计领域解决的问题，包括改进的算法，最小成本的生存网络设计，通过扩展的原始-对偶方法，和概括的Steiner树问题的覆盖要求。 在计算分子生物学领域，研究的领域包括双准则近似方法在物理图谱组装问题中的应用，以及多序列比对中的基本问题-局部，全局和基于树的。 这项职业资助的综合教育计划包括：（a）作为常驻科学家参加DIMACS高中教师计算生物学教育计划，（B）在CMU开发“更现代”的本科跨学科计算生物学，（c）为CMU算法，组合学和优化博士课程的博士生建立和运行研究生研究研讨会，以及（d）开发网络设计和近似算法方面的新研究生课程。

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.***