Collaborative Research: AF: Small: Combinatorial Optimization for Stochastic Inputs

合作研究：AF：小：随机输入的组合优化

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

A central theme in algorithm design is that of making decisions in the presence of uncertainty. In contrast to the usual setting where all the information is available up-front, often the input is not known precisely when we have to make the decisions, but is revealed along the way. We face such decision-making situations all the time, e.g., when deciding on driving routes in the presence of traffic, or dividing our time between chores that take uncertain amounts of time. This project aims to design algorithms for a wide class of such problems using only predictions about the future input. Research on decision-making under uncertainty started nearly seventy years ago, but it has gained much momentum in recent years. This is partly due to numerous applications in scheduling, transportation, electronic commerce etc., and partly because of the vast amounts of data that allow us to make good predictions about the future. This project will model a collection of fundamental and practically relevant problems in this area, and develop techniques to obtain algorithms with provable guarantees on their performance. Research results from this project can bring together communities in computer science with those in operations research, stochastic control and machine learning. The educational component of this project includes the engagement of graduate and undergraduate students in research, and the development of a new graduate course in this subject.The project will model predictions about the uncertain input using probabilistic models. This approach, called stochastic optimization, is one of the most widely-used approaches to model uncertainty. This project aims to make progress on basic problems in scheduling, path-planning and routing, packing and covering, and submodular maximization, in this stochastic setting. The focus of this project will be on two kinds of algorithms for optimization in these settings: non-adaptive algorithms (where all decisions are made in one shot), and adaptive ones (where the decisions are made incrementally, based on random outcomes observed along the way). One of the goals is to broaden the scope of investigation further by considering settings where the underlying random quantities exhibit correlations; this is in contrast to the usual assumptions of independence.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.

算法设计的一个中心主题是在不确定性的情况下做出决策。与所有信息都预先可用的通常设置相反，通常我们在必须做出决策时并不精确地知道输入，而是在沿着显示。我们一直面临这样的决策情况，例如，当在交通中决定驾驶路线时，或者在不确定时间的家务中分配我们的时间时。这个项目的目的是设计一个广泛的一类这样的问题，只使用对未来输入的预测算法。关于不确定性决策的研究始于近70年前，但近年来获得了很大的发展势头。这部分是由于在调度、运输、电子商务等方面的大量应用，部分原因是大量的数据使我们能够对未来做出正确的预测。这个项目将模拟一系列基本的和实际相关的问题在这一领域，并开发技术，以获得算法与可证明的保证其性能。该项目的研究成果可以将计算机科学领域与运筹学、随机控制和机器学习领域的社区聚集在一起。该项目的教育部分包括研究生和本科生参与研究，并在这一主题中开发一个新的研究生课程。该项目将使用概率模型对不确定输入进行建模预测。这种方法称为随机优化，是最广泛使用的不确定性建模方法之一。这个项目的目的是取得进展的基本问题，在调度，路径规划和路由，包装和覆盖，和子模块最大化，在这种随机设置。这个项目的重点将是在这些设置中的两种优化算法：非自适应算法（所有决策都是一次性做出的），和自适应算法（决策是增量式的，基于沿着观察到的随机结果）。目标之一是通过考虑潜在随机量呈现相关性的设置来进一步扩大调查范围;这与通常的独立性假设相反。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

项目成果

Graph Searching with Predictions

• DOI: 10.48550/arxiv.2212.14220
• 发表时间: 2022-12
• 作者: Sid Banerjee;Vincent Cohen-Addad;Anupam Gupta;Zhou Li

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

A Local Search-Based Approach for Set Covering

基于局部搜索的集合覆盖方法

• 发表时间: 2023
• 期刊: 2023 Symposium on Simplicity in Algorithms (SOSA
• 作者: Gupta, Anupam;Lee, Euiwoong;Li, Jason
• 通讯作者: Li, Jason