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局部引理所保证的范围;这个项目的目标是在这个广泛的方向上走得更远，目标是将一个强大的工具，如局部引理的推广在离散优化中有新的应用。