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

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

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.