Studies on New Algorithmic Techniques for Parameterized Computation

许多自然计算问题的NP难度已经成为现实计算世界的强大障碍，在现实世界中，我们正经历着计算机几乎渗透到生活的方方面面。处理实际中的NP-Hard问题已成为不可避免的重要问题。已经提出了一些办法，但没有一种办法完全满足申请中公布的要求。这项拟议的研究研究了一种解决NP-Hard问题的替代方法，参数计算，最近被证明是非常有前途和有用的，特别是在传统方法不适用的情况下。这项研究将强调参数计算与传统计算方法的区别，并开发出有效的、专门用于参数计算的新的、非传统的算法技术。更具体地说，将系统地研究以下参数计算中的新算法技术：(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.