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

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

基本信息

批准号：
2006778
负责人：
Viswanath Nagarajan
金额：
$ 25万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006778&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.

算法设计的一个中心主题是在存在不确定性的情况下做出决策。与所有信息预先提供的通常设置相反，当我们必须做出决定时，通常无法准确地知道输入，而是在过程中被揭示。我们一直面临这样的决策情况，例如，在交通拥堵的情况下决定驾驶路线时，或者在需要不确定时间的家务上分配时间时。该项目旨在仅使用对未来输入的预测来设计针对各种此类问题的算法。不确定性下决策的研究始于近七十年前，但近年来发展势头强劲。这部分是由于调度、运输、电子商务等方面的大量应用，部分是因为大量数据使我们能够对未来做出良好的预测。该项目将对这一领域的一系列基本和实际相关问题进行建模，并开发技术来获得对其性能具有可证明保证的算法。该项目的研究成果可以将计算机科学界与运筹学、随机控制和机器学习界的界人士聚集在一起。该项目的教育部分包括研究生和本科生参与研究，以及开发该学科的新研究生课程。该项目将使用概率模型对不确定输入进行预测。这种方法称为随机优化，是最广泛使用的不确定性建模方法之一。该项目旨在在随机环境中的调度、路径规划和路由、打包和覆盖以及子模最大化等基本问题上取得进展。该项目的重点将是在这些设置中进行优化的两种算法：非自适应算法（所有决策都是一次性做出的）和自适应算法（根据沿途观察到的随机结果逐步做出决策）道路）。目标之一是通过考虑潜在随机量表现出相关性的设置来进一步扩大研究范围；这与通常的独立性假设形成鲜明对比。该奖项反映了 NSF 的法定使命，并且通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。