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

本课题主要研究在两个重要应用领域中出现的NP-Hard问题的近似算法设计：(1)网络设计和(2)计算分子生物学。这项工作包括开发通用技术来解决这两个领域的一类问题，应用和扩展近似算法领域的工具，如原始-对偶模式、双准则公式和近似，以及在性能保证证明中使用图论论点。特别是，在网络设计领域中解决的问题包括通过扩展原始-对偶方法来改进最小费用可生存网络设计的算法，以及具有覆盖要求的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.***