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

CRII：AF：参数中的多项式时间近似方案次指数

• 批准号: 1756014
• 负责人: Lin Chen
• 金额: $ 14.84万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1756014&HistoricalAwards=false
• 关键词: CRII; AF; Polynomial; Time; Approximation

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.

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

项目成果

Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm

受贿选民不确定性的选举：硬度和近似算法

• DOI: 10.1609/aaai.v33i01.33012572
• 发表时间: 2019
• 期刊: Proceedings of the ... AAAI Conference on Artificial Intelligence
• 作者: Chen, L.;Xu, L.;Xu, S. H.;Gao, Z.M.;Shi, W.D.
• 通讯作者: Shi, W.D.