AF: Small: Randomized Algorithms and Stochastic Models

随机性在计算中所起的基本作用是过去四十年来算法和复杂性研究的关键发现之一。这至少以两种方式表现出来：通过随机算法，以及通过不确定数据和/或过程的随机模型。在我们的大数据时代，通过采样等工具（对流和次线性算法至关重要）以及机器学习中通常固有的随机性，这种基本作用得到了强调。在本项目中，PI旨在发展或改进随机算法和随机优化中的一些基本技术，并将其应用于组合优化中的经典和现代问题。本项目将在以下几个方面产生更广泛的影响。研究生将密切参与这项研究，本科生研究团队将接触到算法、概率方法和优化方面的相关思想。通过个人指导和小组教学，高中生将学习这项研究的基础知识，特别是Lovasz局部引理及其各个方面。这项工作的适当方面将被整合到PI的课程中。最后，这项工作将扩展到关键应用领域，包括疫苗接种问题和替代能源工厂的运作。该项目旨在开发具有普遍性和实用性的工具，以及能够改进有针对性的基本应用程序的技术。这些应用包括组合优化中众所周知的问题，如不对称旅行推销员、k中值和随机匹配，以及应用领域的基本问题，如公共卫生和社会网络（疫苗接种）和替代能源（随机不确定性下风能和太阳能发电厂的运营规划）。所提出的技术包括“超越”强大的Lovasz局部引理，局部引理类技术的新迭代应用及其对诸如不对称旅行推销员、依赖舍入关系、子模块化和（矩阵）集中界限等问题的推广，以及离散优化中的新型微分方程技术。作为一个特殊的例子，PI和他的合作者的工作表明，Moser-Tardos算法有一些方面可以帮助我们远远超出Lovasz局部引理所保证的范围；这个项目的目标是在这个广泛的方向上走得更远，目标是推广一个强大的工具，如局部引理，将在离散优化中有新的应用。

The fundamental role played by randomness in computation is one of the key discoveries of research in algorithms and complexity over the last four decades. This manifests itself in at least two ways: through randomized algorithms, and through stochastic models for uncertain data and/or processes. This fundamental role has been accentuated in our Big Data age through tools such as sampling which are vital for streaming and sub-linear algorithms, as well as through the stochasticity that is often inherent in machine learning. In this project, the PI aims to develop or improve some basic techniques in randomized algorithms and stochastic optimization, as well as to apply them to classical and modern problems in combinatorial optimization.The broader impact of this project will be in several directions including the following. Graduate students will be involved closely in this research, and undergraduate research teams will be exposed to related ideas in algorithms, probabilistic methods, and optimization. High-school students will be taught the foundations of this research, especially the Lovasz Local Lemma and its facets, both through individual mentoring and through group-based teaching. Appropriate aspects of this work will be integrated into the PI's classes. Finally, this work will extend to key applications in areas including vaccination problems and the operation of alternative-energy plants.This project aims to develop tools that will be general and useful in their own right, as well as techniques that will lead to improvements for targeted, fundamental applications. These applications include well-known problems in combinatorial optimization including asymmetric traveling salesperson, k-median, and stochastic matching, as well as basic issues in application areas such as public health and social networks (vaccination) and alternative energy (operations planning for wind and solar energy plants under stochastic uncertainty). The proposed techniques encompass "going beyond" the powerful Lovasz Local Lemma, new iterated applications of Local Lemma-like techniques and their generalizations to problems such as asymmetric traveling salesperson, the nexus of dependent rounding, submodularity, and (matrix) concentration bounds, as well as new types of differential-equation techniques in discrete optimization. As a particular example, work of the PI and his collaborators has shown that the Moser-Tardos algorithm has facets that can help us get well beyond what is guaranteed by the Lovasz Local Lemma; this project aims to go significantly further in this broad direction, with the goal that generalizations of a powerful tool such as the Local Lemma will have new applications in discrete optimization.