权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Pragmatic Parameterized Algorithms

实用的参数化算法

基本信息

批准号：
221760991
负责人：
Professor Dr. Peter Rossmanith
金额：
--
依托单位：
Informatik 1 - Lehrgebiet Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2014-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/221760991?language=en
关键词：
Pragmatic Parameterized Algorithms

项目摘要

The paradigms of fixed-parameter and moderately exponential algorithmshave been spectacularly successful in obtaining efficient algorithms fora number of NP-complete problems. Many of these algorithms are, however,purely theoretical in the sense that they are not implementable in areal-world setting, i.e., under tight time and cost constraints. Forinstance, there are algorithms that rely on algorithmic meta-theorems - results that hold not just for a few isolated problemsbut for a whole class of problems. While meta-theorems are immensely useful inquickly establishing whether a problem at hand admits an algorithm of aparticular type, they are usually not very useful in designing algorithmsin practice. Then again there are algorithms that use deep structural theoremssuch as the Graph Minors Theorem. Such algorithms are not implementable either. Finally there are algorithms that use structural parameters that are themselves hardto compute. Efficient FPT-algorithms wrt these parameters might not be efficient in practice. The broad goal of this project is to bridge the gap between purely theoretical algorithmsand heuristics that are extensively used in practice but which produce solutions without any quality guarantee. In particular, we seek to develop efficient algorithms that are (1) easily translatable into programs and run successfully under real-worldconstraints; and, (2) competitive with or even faster than the currentbest algorithms in their asymptotic behavior. Our main aim is to improve and create new algorithmic techniques in order to take a stepforward towards implementability. These new algorithmic techniques themselves be complex or have the flavor of meta-theorems but we areinterested in those which are amenable to implementation.The real-world constraints we have in mind include implementation time,space requirements and running time guarantees. By providing transparenttime and space bounds, i.e., by keeping polynomial and constants factorswithin reasonable limits, we wish to push the envelope of algorithmsthat can eventually be engineered for use in industry andapplications.

固定参数算法和中等指数算法的范例在获得许多NP完全问题的有效算法方面取得了巨大的成功。然而，这些算法中的许多是纯理论的，因为它们在现实世界设置中是不可实现的，即，在严格的时间和成本限制下。例如，有些算法依赖于算法元定理--这些结果不仅适用于少数孤立的问题，而且适用于整个一类问题。虽然元定理在快速确定一个问题是否允许一个特定类型的算法方面非常有用，但它们在实际设计算法时通常不是很有用。还有一些算法使用了深层的结构定理，比如图次定理。这样的算法也是不可实现的。最后，还有一些算法使用的结构参数本身就很难计算。这些参数的有效FPT算法在实践中可能不是有效的。这个项目的广泛目标是弥合纯理论算法和在实践中广泛使用但没有任何质量保证的解决方案之间的差距。特别是，我们寻求开发高效的算法，（1）容易翻译成程序，并在现实世界的约束下成功运行;和，（2）竞争，甚至比当前最好的算法在其渐近行为更快。我们的主要目标是改进和创建新的算法技术，以便向可实现性迈进一步。这些新的算法技术本身是复杂的或具有元定理的味道，但我们感兴趣的是那些易于实现的，我们考虑的现实世界的约束包括实现时间，空间要求和运行时间保证。通过提供连续的时间和空间边界，即，通过将多项式和常数因子保持在合理的范围内，我们希望推动算法的包络，最终可以在工业和应用中使用。