CRII: AF: Polynomial Time Approximation Schemes Subexponential in the Parameter

算法在我们的日常生活中非常重要，因为它们极大地提高了各个领域的任务执行效率。人们在不知不觉中享受着智能手机、笔记本电脑和家用机器人中使用的算法带来的好处。各种声称聪明并更好地服务于人们需求的产品，都要归功于其中实现的智能算法。因此，对基本问题算法的改进将对人们的生活乃至整个社会产生重大影响。该项目旨在进一步完善各种基本问题的算法，包括调度、资源分配和路由问题。有趣的是，许多这类问题的算法可以进一步改进，这既有趣，也令人惊讶，这些问题似乎承认运行时间可能是最佳的。该项目还将通过为不同背景的研究生和本科生编写新的教材，为教育做出重大贡献。研究助理将参与该项目的所有领域。细粒度复杂性是一个研究领域，其目的是在复杂性理论中提供一种精细的分类，重点是对解决问题所需的确切时间进行定量研究。这一领域的研究大多集中在精确算法上。本项目旨在将细粒度复杂性的研究扩展到近似算法的方向。特别是，我们提出了一个定量的研究参数的相依性来衡量近似格式的精度，特别是这个参数的次指数相依性。该项目试图挑战调度、资源分配和路线选择中的几个经典问题，这些问题允许近似方案似乎具有最佳运行时间并保持数十年不变。它将通过建立在精度参数中以次指数形式运行的近似方案来打破常规的障碍。它将探索近似方案中的这种次指数现象，并将其与已被广泛观察到的参数化复杂性领域的次指数现象进行比较。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Algorithms are important to our everyday life as they have greatly improved the efficiency of task performance in various areas. People are enjoying the benefits brought by algorithms used in their smartphones, laptops and household robots without even realizing it. Various products that are claimed to be clever and better serve people's needs owe their smartness to the smart algorithms implemented in them. Therefore, the improvement on algorithms for fundamental problems will have a significant impact to people's life as well as the whole society. This project aims at further improving the algorithms for various fundamental problems including scheduling, resource allocation and routing problems. It is interesting and meanwhile surprising that the algorithms for many such problems, which seem to admit the best possible running time, can be further improved. The project will also make significant contributions to education via new teaching materials for graduate and undergraduate students with diverse backgrounds. Research assistants will participate in all areas of this project. Fine-grained complexity is a research field that aims to provide a refined classification in complexity theory with a focus on a quantitative study of the exact time required to solve problems. Most researches in this area are concerned with exact algorithms. This project aims at extending the research of fine-grained complexity in the direction of approximation algorithms. In particular, we propose a quantitive study on the dependency of the parameter that measures the accuracy in approximation schemes, with a particular focus on the subexponential dependency of this parameter. The project seeks to challenge several classical problems in scheduling, resource allocation and routing which admit approximation schemes that seem to have a best running time and remain untouched for decades. It will break the barrier of convention by establishing approximation schemes that run in time that is subexponential in the accuracy parameter. It will explore such a subexponential phenomenon in approximation schemes and compare it with the subexponential phenomenon in the field of parameterized complexity, which has been widely observed.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.