AF: Small: New Approaches for Approximation and Online Algorithms

AF：小：近似和在线算法的新方法

• 批准号: 1907820
• 负责人: Anupam Gupta
• 金额: $ 30万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1907820&HistoricalAwards=false
• 关键词: AF; Small; New; Approaches; Approximation

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.

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

项目成果

Optimal Bounds for the k -cut Problem

k 割问题的最优界

• DOI: 10.1145/3478018
• 发表时间: 2022
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Gupta, Anupam;Harris, David G.;Lee, Euiwoong;Li, Jason
• 通讯作者: Li, Jason

Random Order Online Set Cover is as Easy as Offline

随机订购在线套装封面与离线一样简单

• DOI: 10.1109/focs52979.2021.00122
• 发表时间: 2022
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Gupta, Anupam;Kehne, Gregory;Levin, Roie
• 通讯作者: Levin, Roie

Chasing Convex Bodies with Linear Competitive Ratio

以线性竞比追逐凸体

• DOI: 10.1145/3450349
• 发表时间: 2021
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Argue, C. J.;Gupta, Anupam;Tang, Ziye;Guruganesh, Guru
• 通讯作者: Guruganesh, Guru

Caching with Time Windows and Delays

使用时间窗口和延迟进行缓存

• DOI: 10.1137/20m1346286
• 发表时间: 2022
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Gupta, Anupam;Kumar, Amit;Panigrahi, Debmalya
• 通讯作者: Panigrahi, Debmalya

Robust Secretary and Prophet Algorithms for Packing Integer Programs

用于打包整数程序的鲁棒秘书和先知算法

• DOI: 10.1137/1.9781611977073.53
• 发表时间: 2022
• 期刊: 2022 ACM-SIAM Symposium on Discrete Algorithms
• 作者: Argue, C. J.;Gupta, Anupam;Molinaro, Marco;Singla, Sahil
• 通讯作者: Singla, Sahil