Parameterized Approximation - new concepts and new applications

大约40年前，NP-硬度的概念被开发出来。许多组合问题被证明是NP难的。这意味着他们不应该有有效的解决算法。从技术上讲，为任何NP完全问题找到一个确定性多项式时间算法都需要为所有NP完全问题找到确定性多项式时间算法。一般认为这是不可能的，但迄今为止还没有找到这个猜想的数学证明。实际上，这个问题是我们当今最重要的数学问题之一。由于NP完全组合问题往往是对实际应用很重要的问题的模型，（至少）两种算法开发策略已被建议和研究，（理论）计算机科学：（a）近50年来，已经开发出多项式时间算法，这些算法不能找到给定问题实例的最佳解，而只能找到近似解，但有一定的性能保证。(b)近20年来，精确参数化复杂性提供了另一种方法，试图将NP完全问题的精确算法的看似不可避免的组合爆炸限制在输入的一小部分，即所谓的参数上，这两种方法都有其局限性，可以通过复杂性理论的方法来证明。这促使联合收割机结合这两种方法，导致参数化近似的想法，这是一个近年来开始的领域。在这个项目中，我们努力为这种算法找到新的方法。例如，许多多项式时间近似算法是基于数学优化（最著名的是线性规划（ILP）），而这不是参数化算法的情况，无论是精确的还是近似的。人们自然会问ILP技术是否或如何用于开发参数化近似算法。相反，有一些算法思想，如迭代压缩，对于精确的参数化算法来说是最重要的，但迄今为止还没有以真正的方式用于参数化近似，这是我们想要实现的另一项任务。为了解决这些方法论问题，我们将解决具体的组合问题。2我们希望从数据安全的领域来关注这些问题。首先，这一领域的重要性在最近变得更加明显，其次，迄今为止还没有对相应的组合问题进行系统的研究。有了这笔赠款，我们想支付一名博士生谁已被证明是特别合格的，因为她学习了两个科目，计算机科学和数学。无论是建模方面（在数据安全），并为准确和近似算法的发现，我们要求墨卡托研究员帮助我们在项目中。

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.