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

Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques

NP 难问题的算法工程：参数化算法与现有技术

基本信息

批准号：
230839996
负责人：
Dr. Falk Hüffner
金额：
--
依托单位：
Institut für Softwaretechnik und Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2013
资助国家：
德国
起止时间：
2012-12-31 至 2014-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/230839996?language=en
关键词：
Algorithm Engineering NP hard Problems

项目摘要

Many combinatorial problems from diverse application areas such as biology, operations research, or data mining, are NP-hard. In practice, mainly heuristics or mathematical programming (ILPs) are employed for such problems; however, these typically lack guarantees on solution quality or guarantees on running time. Parameterized algorithms are a recent approach that tries to solve problems from practice optimally in provably bounded time. Although there is much progress in the theory and the field has the explicit claim of applicability, there are few works on implementation and experiments with real-world data that lead to practically deployable software. In this project, first based on parameterized algorithmics new methods for solving NP-hard problems will be developed; these will then be implemented and compared to conventional technique approaches, in order to reach generel recommendations. Further, parameterized techniques will be used to improve heuristics and ILP approaches. In this way, it will be examined how far parameterized algorithmics can hold up to the claim of delivering practically relevant solution methods. For this, also general principles and instructions will be developed that show how to attack a hard problem with the methods of parameterized algorithmics.

来自不同应用领域（如生物学、运筹学或数据挖掘）的许多组合问题都是NP难问题。在实践中，主要是数学规划或数学规划（ILP）用于此类问题;然而，这些通常缺乏对解决方案质量或运行时间的保证。参数化算法是一种尝试在可证明的有界时间内最优地解决实践问题的新方法。虽然在理论上有很大的进步，该领域有明确的适用性要求，但很少有实际数据的实现和实验，导致实际可部署的软件。在这个项目中，首先将开发基于参数化算法的解决NP难题的新方法;然后将实施这些方法并与传统技术方法进行比较，以达到generel建议。此外，参数化技术将被用来改善并行计算和ILP方法。通过这种方式，我们将研究参数化算法在多大程度上能够满足提供实际相关解决方案的要求。为此，还将制定一般原则和说明，说明如何使用参数化算法的方法来解决难题。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Fixed-parameter algorithms for DAG Partitioning

DAG 分区的固定参数算法

DOI：
10.1016/j.dam.2016.12.002
发表时间：
2017
期刊：
Discret. Appl. Math.
影响因子：
0
作者：
R. van Bevern;R. Bredereck;M. Chopin;S. Hartung;F. Hüﬀner;A. Nichterlein;O. Suchý
通讯作者：
O. Suchý

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage

将生物网络划分为具有最大边缘覆盖的高度连接的集群