AF: Small: New Approaches for Approximation and Online Algorithms

近似算法的领域集中在NP难优化问题，并获得快速算法，输出接近最优的解决方案，说在多项式时间。在在线算法领域，随着时间的推移，输入会慢慢显露出来，目标是在不知道输入的未来部分的情况下获得好的算法。在这个项目中考虑的许多问题是NP难的，并且通常所产生的问题不是静态问题而是动态问题，因此这些领域是算法设计的核心。该研究项目旨在开发这两个领域的新技术，在一些长期存在的开放问题上取得进展。例如，它旨在开发通用工具来解决在线输入时的凸优化问题：鉴于凸优化是算法和机器学习中许多技术的基础，这些结果在计算机科学内外都具有广泛的适用性。该项目的研究部分与教育和培训部分密切相关，包括培训研究生和本科生，以及开发新课程和材料。在该项目中，目标是将迄今为止不同的技术结合起来，并使用它们的组合来解决一些核心问题。例如，许多NP难问题已经被攻击，一方面，随机化和凸优化的工具，另一方面，固定参数的易处理性的角度，其中算法被允许在某些参数的指数。该项目希望将这些领域结合在一起，并使用这种想法的综合来进一步发展k-割划分问题和k-均值聚类问题等方面的最新技术。近似算法的这种细粒度概念应该会导致对这些基本问题的新的结构性见解。在在线算法方面，希望将来自持续优化和在线学习的思想与在线算法设计中通常使用的组合思想相结合，以在k服务器和在线凸最小化等问题上取得进展。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

The area of approximation algorithms focuses on NP-hard optimization problems, and on obtaining fast algorithms that output solutions that are near-optimal, say in polynomial time. In the area of online algorithms, the input is revealed slowly over time, and the goal is to get good algorithms without knowing the future portions of the input. Many questions considered in this project are NP-hard, and often the resultant problems are not static problems but dynamic ones, hence these areas are central to algorithm design. This research project aims to develop new techniques in both these areas, to make progress on some long-standing open problems. For instance, it aims to develop general tools to solve convex optimization problems when the input appears online: given that convex optimization underlies many techniques in algorithms and machine learning, such results have broad applicability both within computer science and beyond. The research component of this project goes hand-in-hand with its educational and training component, which will include training both graduate and undergraduate students, and in developing new courses and materials.In this project, the goal is to bring together hitherto disparate techniques, and use their combination to solve some central questions. For instance, many NP-hard problems have been attacked using, on one hand, the tools of randomization and convex optimization, and on the other, the perspective of fixed-parameter tractability, where the algorithm is allowed to be exponential in some parameter. The project hopes to bring these areas together, and use this synthesis of ideas to further the state-of-the-art on the k-cut partitioning problems and k-means clustering problems, among others. This fine-grained notion of approximation algorithms should lead to new structural insights into these fundamental questions. In online algorithms, the hope is to use ideas from continuous optimization and online learning, in combination with the combinatorial ideas typically used in the design of online algorithms, to make progress on problems like k-server and online convex minimization.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.