AF: Small: Randomized Algorithms and Stochastic Models

AF：小：随机算法和随机模型

• 批准号: 1422569
• 负责人: Aravind Srinivasan
• 金额: $ 45万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-06-01 至 2019-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422569&HistoricalAwards=false
• 关键词: AF; Small; Randomized; Algorithms; Stochastic

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.

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