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年前，但近年来它已经获得了很多动力。这部分是由于在调度，运输，电子商务等方面的众多申请，部分原因是大量数据使我们能够对未来做出良好的预测。该项目将模拟该领域的基本和实际相关问题的集合，并开发技术以获取具有可证明其性能保证的算法。该项目的研究结果可以将计算机科学的社区与运营研究，随机控制和机器学习的社区汇集在一起。该项目的教育组成部分包括研究生和本科生参与研究，以及在此主题中开发新的研究生课程。该项目将使用概率模型对不确定输入的预测进行建模。这种称为随机优化的方法是建模不确定性的最广泛使用的方法之一。该项目旨在在此随机环境中的调度，路径规划和路由，包装和覆盖以及supperdular最大化方面的基本问题取得进展。该项目的重点将放在在这些设置中进行优化的两种算法：非自适应算法（其中所有决策都一击做出）和自适应算法（基于在途中观察到的随机结果逐渐做出决策）。目标之一是通过考虑潜在的随机数量表现出相关性的环境，进一步扩大调查范围；这与普通的独立假设相反。该奖项反映了NSF的法定使命，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查标准来评估值得支持的。