近似算法的设计与分析

在计算机科学、信息科学、生命科学及密码科学等新兴科技领域中不断遇到大量的数学计算问题，它们大多具有组合最优化的特性。众所周知，几乎所有组合最优化问题都是NP-困难的，因此，人们几乎没有可能在多项式时间内求得这些问题的精确解。所以，这些亟待解决而又难于解决的问题的高效近似算法的设计与分析研究有着重要的现实意义。鉴于科学技术研究和社会实践需要对数学问题高效近似计算方面的迫切要求，本项目将集中精力解决新兴科技领域中出现的具有离散特点的数学计算问题，即组合优化问题的算法设计与分析。在研究这些来之新兴科技领域并急需解决的组合最优化问题的算法的同时，做深入的理论分析是计算机科学的重要组成部分，我们试图通过交叉学科研究来带动组合最优化与计算机科学的迅猛发展。