EAGER: Probabilistic Models and Algorithms

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

The power of randomness in the computational context is one of the key discoveries of computer science. This project studies algorithms for fundamental problems that will further explore and use such power offered by randomness. One example of such a basic problem considered is in facility location: how can we place facilities at a low cost in order to minimize the total commute time for the customers? This classical problem has significant modern applications as well: e.g., in clustering data for machine learning, and in placing services on the Internet cloud. The PI aims to resolve how best this -- and closely-related problems in clustering and facility location -- can be solved via new probabilistic techniques. The PI will also study other such fundamental problems (e.g., in efficient resource allocation) in optimization through randomized algorithms, as well as study how such investigations improve and/or develop broadly-applicable probabilistic techniques. This project aims to have broader impact also through human-resource development. A graduate student will be directly involved in almost all this proposed research. The PI has advised two multi-year ``Gemstone" undergraduate research teams: both teams have had their research published in national conferences. The PI proposes to start advising a new such team around 2018 and continue to expose them to the interplay between algorithms, randomness, and networks. Furthermore, the PI will mentor two high-school students; these students will continue to learn algorithms, randomness and applications from their basics up to cutting-edge research. The research of one of these high-school students, co-mentored by the PI, was invited to compete in the Intel International Science and Engineering Fair in 2017. A substantial part of this project will be on developing improved approximation algorithms through (new techniques in) randomization: approximation algorithms are those that are provably efficient and deliver solutions that are within a provable distance from optimal. Two representative examples of problems considered in this regard are in facility location (opening a subset of a given set of facilities in order to minimize the sum of the facility-opening costs and the total commute-time of the customers, as well as variants of this classical problem), and assigning jobs to servers in a general setting, in order to minimize the sum of the completion times of the jobs (weighted by individual priorities of the jobs). Methodologically, this project proposes to develop new techniques to carefully "round" infeasible solutions to feasible solutions via randomization, to further understand the power of information-theoretic notions (e.g., when one has a range of choices of probability distribution for the random choices to be made, can choosing a distribution that maximizes the entropy offer additional power?), and the interplay between linear-algebraic and probabilistic arguments. The "rounding" approach is flexible and general: e.g., for the facility location and job-assignment problems, it is computationally easy to start with near-optimal but infeasible solutions, and the key open question is how to optimally round to a feasible solution. Advances in such rounding techniques have had numerous consequences in approximation algorithms; a key goal of this project is to contribute to further such advances.