Studies on New Algorithmic Techniques for Parameterized Computation

许多自然计算问题的NP难性已经成为真实的计算世界的一个强大障碍，在这个世界里，我们正在经历计算机对生活的几乎所有方面的渗透。在实践中处理NP难问题变得越来越重要。已经提出了一些方法，但没有一个完全满足应用程序中的要求。这项研究提出了一种解决NP难问题的替代方法，参数化计算，最近被证明是非常有前途和有用的，特别是当传统方法不适用时。该研究将强调参数化计算与传统计算方法的区别，并开发新的和非传统的算法技术，是有效的和特殊的参数化计算。更具体地说，以下新的算法技术参数计算将系统地研究：（1）参数对偶界;（2）小的未知子集的有效处理;（3）新的参数化算法的分析技术;（4）参数化计算下界;和（5）参数化算法库。该研究的成功将极大地促进我们对计算易处理性和计算难处理性概念的理解，并为解决真实的计算世界中的困难计算问题提供有效的技术和解决方案。

The NP-hardness of many natural computational problems has become a strong obstacle to the real world of computing, where we are experiencing a pervasion of virtually all aspects of life by computers. Dealing with NP-hard problems in practice has become unavoidably important. A number of approaches have been proposed but none of them has perfectly satisfied the requirements posted in applications. This proposed research studies an alternative approach to NP-hard problems, parameterized computation, which has recently turned out to be very promising and useful, in particular when traditional approaches are not applicable. The research will emphasize the difference between parameterized computation and traditional computational approaches, and develop new and non-traditional algorithmic techniques that are effective and special for parameterized computation. More specifically, the following new algorithmic techniques in parameterized computation will be systematically investigated: (1) parameter dual bounds; (2) effective process of small unknown subsets; (3) new analysis techniques for parameterized algorithms; (4) parameterized computational lower bounds; and (5) parameterized algorithm libraries. The success of the proposed research will significantly advance our understanding on the concepts of computational tractability and intractability, and provide effective techniques and solutions for solving difficult computational problems in the real world of computing.