Studies on New Algorithmic Techniques for Parameterized Computation

参数化计算新算法技术研究

• 批准号: 0830455
• 负责人: Jianer Chen
• 金额: $ 15万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-10-01 至 2011-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830455&HistoricalAwards=false
• 关键词: Studies; New; Algorithmic; Techniques; Parameterized

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.

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