几何优化的近似算法

许多NP-困难组合最优化问题本质上是几何类的问题，近年来出现了一些利用几何特性来生成好的近似算法的精致方法。成功的例子包括著名的平面旅行商问题、平面Steiner树问题等，但仍有许多问题是现有技术所不能及的。我们将对近似算法开展系统研究，这既包含新方法论的研发，也包括对现有技术不易处理的诸如带有障碍的Steiner树、曲面近似等特定问题的求解。除了这些经典问题外，我们打算在这一框架下对无线和遥感网络中所产生的新型问题进行探讨。例如，特定无线网络中不同路由选择策略、频率与区域指派问题等均可描述为适当几何图中的最优化问题。最后，我们也希望发展一个相应的复杂性理论来对这些问题按它们的困难程度进行分类，以便对这些问题之间的关系能有一个更深层次的了解。所获结果有望用于计算生物学、计算机和通信网络（开关网络、光纤网络和无线网络）以及网络安全等领域中出现的组合优化问题的近似算法设计。