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

点击翻译按钮获取中文摘要

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.