Studies on New Algorithmic Techniques for Parameterized Computation

许多自然计算问题的np硬度已经成为现实计算世界的一个强大障碍，在现实世界中，我们正在经历计算机几乎渗透到生活的各个方面。处理NP-hard问题在实践中变得不可避免的重要。已经提出了许多方法，但没有一种能够完全满足应用程序中发布的要求。本研究提出了一种np困难问题的替代方法，参数化计算，最近被证明是非常有前途和有用的，特别是在传统方法不适用的情况下。研究将强调参数化计算与传统计算方法的区别，并开发新的和非传统的算法技术，这些算法技术对参数化计算是有效的和特殊的。更具体地说，将系统地研究参数化计算中的以下新算法技术：(1)参数对偶界；(2)小未知子集的有效处理；(3)参数化算法的新分析技术；(4)参数化计算下界；参数化算法库。本研究的成功将极大地促进我们对计算可跟踪性和难处理性概念的理解，并为解决现实计算世界中的计算难题提供有效的技术和解决方案。

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.