Parameterized Approximation - new concepts and new applications

参数化逼近——新概念和新应用

• 批准号: 259237183
• 负责人: Professor Dr. Henning Fernau
• 金额: --
• 依托单位: Lehrstuhl für Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2017-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/259237183?language=en
• 关键词: Parameterized; Approximation; new; concepts; applications

About 40 years ago, the notion of NP-hardness was developed. Many combinatorial problems were shown to be NP-hard. This means that they are supposed not to have efficient solving algorithms. More technically speaking, finding a deterministic polynomial-time algorithm for any of the NP-complete problems would entail having deterministic polynomial-time algorithms for all of them. It is generally believed that this is impossible, but hitherto no mathematical proof for this conjecture has been found. Actually, this question is one of the most important mathematical questions of our days.As NP-complete combininatorial problems often model questions that are important for practical applications, (at least) two algorithm development strategies have been suggested and investigated in (Theoretical) Computer Science: (a) Since nearly 50 years, polynomial-time algorithms have been developed that do not find optimal solutions to a given problem instance, but only approximative ones, but with a certain performance guarantee.(b) Since nearly 20 years, exact parameterized complexity offers an alternative approach, trying to restrict the seemingly inevitable combinatorial explosion of exact algorithms for NP-complete problems to a hopefully small part of the input, the so-called parameter.Both approaches have their limits that can be shown by complexity-theoretic means. This motivates to combine both approaches, leading to the idea of parameterized approximation, a field that started out in recent years.Yet, this idea is in its infancy. Within this project, we strive to find new ways for such algorithms. For instance, many polynomial-time approximation algorithms are based on Mathematical Optimization (most notably, Integer Linear Programming (ILP)), while this is not the case for parameterized algorithms, be them exact or approximative. It is natural to ask if or how ILP techniques can be used to develop parameterized approximation algorithms.Conversely, there are algorithmic ideas like iterative compression that are most important for exact parameterized algorithms, but that have not been used so far in a genuine fashion for parameterized approximation, which is another task we want to achieve.To solve these methodological questions, we will tackle concrete combinatorial problems.We want to focus on such problems from the area of Data Security. First, the importance of this area became much more clear in recent times, and secondly, no systematic study of the according combinatorial problems has been undertaken so far.With this grant, we like to pay one PhD student who has proven to be particularly eligible, as she studied two subjects, Computer Science and Mathematics. Both for the modeling aspect (in Data Security) and for the finding of exact and approximative algorithms, we ask for a Mercator fellow to help us in the project.

大约40年前，NP硬度的概念被提出。许多组合问题被证明是NP难的。这意味着他们应该没有有效的求解算法。从技术上讲，找到任何NP完全问题的确定性多项式时间算法都需要对所有这些问题都有确定性多项式时间算法。人们普遍认为这是不可能的，但到目前为止还没有找到这个猜想的数学证明。事实上，这个问题是当今最重要的数学问题之一。由于NP完全组合问题经常模拟对实际应用很重要的问题，(至少)在(理论)计算机科学中已经提出和研究了两种算法开发策略：(A)近50年来，已经发展出多项式时间算法，它们不能找到给定问题实例的最优解，而只找到近似解，但具有一定的性能保证。(B)近20年来，精确参数化复杂性提供了一种替代方法，试图将NP-完全问题的精确算法的组合爆炸限制在输入的一小部分，即所谓的参数，这两种方法都有其局限性，可以用复杂性理论的方法来证明。这促使人们将这两种方法结合起来，产生了参数逼近的概念，这是近年来兴起的一个领域。然而，这个想法还处于起步阶段。在这个项目中，我们努力为这类算法找到新的方法。例如，许多多项式时间近似算法基于数学最优化(最著名的是整数线性规划(ILP))，而这不是参数化算法的情况，无论它们是精确的还是近似的。我们很自然地会问ILP技术是否或如何被用来开发参数化逼近算法。相反，迭代压缩等算法思想对于精确的参数化算法是最重要的，但到目前为止还没有真正用于参数化逼近，这是我们想要实现的另一项任务。为了解决这些方法论问题，我们将解决具体的组合问题。我们想从数据安全的角度来关注这些问题。首先，这一领域的重要性在最近变得更加明显，其次，到目前为止，还没有对相应的组合问题进行系统的研究。有了这笔补助金，我们愿意支付一名被证明特别有资格的博士生，因为她学习了两门学科，计算机科学和数学。无论是在建模方面(在数据安全方面)，还是在寻找精确和近似的算法方面，我们都需要一位墨卡托研究员来帮助我们完成这个项目。