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-硬性优化问题，并获得了在多项式时间内输出近似最佳解决方案的快速算法。在在线算法的领域中，随着时间的推移，输入的揭示缓慢，目标是在不知道输入的未来部分的情况下获得良好的算法。该项目中考虑的许多问题都是NP-HARD，通常问题不是静态问题，而是动态问题，因此这些领域是算法设计的核心。该研究项目旨在在这两个领域开发新技术，以在一些长期的开放问题上取得进展。例如，它旨在开发一般工具以在线出现在线出现时解决凸优化问题：鉴于凸优化是算法和机器学习中许多技术的基础，因此这些结果在计算机科学及其他地区都具有广泛的适用性。该项目的研究组成部分与其教育和培训组成部分息息相关，其中包括培训研究生和本科生，以及开发新课程和材料。在该项目中，目标是将迄今为止截然不同的技术汇总在一起，并利用其组合来解决一些中心问题。例如，一方面，已经攻击了许多NP - 硬性问题，而随机化和凸优化的工具，另一方面，固定参数障碍性的角度，其中允许算法在某些参数中指数为指数。该项目希望将这些领域融合在一起，并利用这种思想的综合来进一步发展K-Cut分区问题和K-均值聚类问题等。这种近似算法的细粒度概念应导致对这些基本问题的新结构见解。 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.

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

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
影响因子：
0
作者：
Gupta, Anupam;Kehne, Gregory;Levin, Roie
通讯作者：
Levin, Roie

Online Discrepancy with Recourse for Vectors and Graphs

向量和图形的在线差异

DOI：
10.1137/1.9781611977073.57
发表时间：
2022
期刊：
2022 ACM-SIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Gupta, Anupam;Gurunathan, Vijaykrishna;Krishnaswamy, Ravishankar;Singla, Sahil
通讯作者：
Singla, Sahil

Bag-Of-Tasks Scheduling on Related Machines