AF: Small: Hardness of Approximation Meets Parameterized Complexity

AF：小：近似难度满足参数化复杂性

• 批准号: 2313372
• 负责人: Karthik Srikanta
• 金额: $ 60万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-01 至 2026-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2313372&HistoricalAwards=false
• 关键词: AF; Small; Hardness; Approximation; Meets

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.

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