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的法定任务，并已通过评估该基金会的智力优点和广泛的影响来评估Criteria，并被认为是值得通过评估的支持。

项目成果

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.