AF: Small: Randomized Algorithms and Stochastic Models

点击翻译按钮获取中文摘要

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.