AF: Small: Hardness of Approximation Meets Parameterized Complexity

许多重要的优化问题是不容易处理的。科普优化问题的棘手性的两种典型方法是设计找到其成本接近最优的解决方案的算法，或者设计找到精确解决方案但在时间上运行的算法，其输入大小纯粹是多项式的，但在问题的参数方面是指数的（或可能更糟）（称为固定参数易处理性运行时间）。对于几个优化问题，可以证明（i）找到好的近似解和找到最优解一样困难，以及（ii）对于感兴趣的特定参数，在合理的假设下，该问题不允许具有固定参数易处理性运行时的算法。事实上，对于许多重要的问题，有可能证明，对于特定的参数的利益，并在合理的假设下，该问题甚至不承认算法计算只有一个近似的解决方案，而具有固定的参数易处理运行时间。这个项目关注的是这种不可逼近性结果的研究。该项目的研究目标将与教学，辅导和传播活动相结合。该研究将涉及研究生和博士后研究员的参与。该项目涉及开发由近似的硬度和参数化复杂性的交叉产生的新生领域的挑战性任务，从编码理论，极值组合学和布尔函数分析的工具包中提取。计划在这个项目中调查的问题基本上是在20世纪90年代在非确定性多项式（NP）世界中追求的相同问题，然后形成了近似结果硬度的基石。在NP世界中，这些结果（以及开发的技术）作为起点来证明理论计算机科学社区感兴趣的各种其他问题（如聚类，旅行推销员问题，调度问题等）的不可近似性。一旦成功回答了这个项目中的问题，参数化复杂性领域的研究人员将有足够的结果和工具来证明他们感兴趣的问题的近似性的难度。这个奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many important optimization problems are not tractable. Two typical ways to cope with the intractability of optimization problems is to either design algorithms that find solutions whose cost is close to the optimum or design algorithms which find exact solutions but run in time purely polynomial in the input size but exponential (or possibly worse) in terms of a parameter of the problem (referred to as fixed parameter tractability runtime). For several optimization problems, it is possible to prove that (i) finding good approximate solutions is as hard as finding optimal solutions, and (ii) for specific parameters of interest, under plausible assumptions, the problem does not admit algorithms with fixed parameter tractability runtime. In fact, for many important problems, it is possible to prove that for specific parameters of interest, and under plausible assumptions, the problem does not even admit algorithms computing only an approximate solution while having fixed parameter tractability runtime. This project concerns the study of such inapproximability results. The research goals of the project will be integrated with teaching, mentoring, and dissemination activities. The research will involve participation of graduate students and post- doctoral fellows.This project deals with the challenging task of developing the nascent area arising from the intersection of hardness of approximation and parameterized complexity, drawing from toolkits in coding theory, extremal combinatorics, and analysis of Boolean functions. The problems that are planned to be investigated in this project are essentially the same problems pursued in the 1990s in the non-deterministic polynomial (NP) world which then formed the bedrock of hardness of approximation results therein. In the NP world, these results (and the techniques developed) served as the starting point to prove the inapproximability of various other problems of interest to the Theoretical Computer Science community (such as Clustering, Travelling Salesman Problem, Scheduling problems, etc.). Upon successfully answering the questions in this project, researchers in parameterized complexity will have sufficient results and tools at their disposal to prove the hardness of approximation for the problems of their interest.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.