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.