AF: Small: Hardness of Approximation Meets Parameterized Complexity

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

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.