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

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

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.