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

本项目侧重于在两个重要应用领域(1)网络设计和(2)计算分子生物学中出现的np困难问题的近似算法设计。这项工作涉及到解决这两个领域的问题的一般技术的发展，应用和扩展近似算法领域的工具，如原始对偶模式，双准则公式和近似，以及在性能保证的证明中使用图论论证。特别是，在网络设计领域解决的问题包括通过扩展原始对偶方法改进的最小成本生存网络设计算法，以及覆盖需求的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.***