AF: Small: Randomized Algorithms and Stochastic Models

随机性在计算中扮演的基本角色是过去40年来算法和复杂性研究的关键发现之一。这至少通过两种方式表现出来：通过随机化的算法，以及通过不确定数据和/或过程的随机模型。在我们的大数据时代，通过采样等对流和次线性算法至关重要的工具，以及机器学习通常固有的随机性，这种基本作用得到了强调。在这个项目中，PI旨在发展或改进随机算法和随机优化中的一些基本技术，并将它们应用于组合优化中的经典和现代问题。该项目将在几个方向产生更广泛的影响。研究生将密切参与这项研究，本科生研究团队将接触到算法、概率方法和优化方面的相关想法。高中生将通过个人辅导和小组教学，学习这项研究的基础，特别是洛瓦兹局部引理及其各方面。这项工作的适当方面将被整合到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.