EAGER: Probabilistic Models and Algorithms

随机性在计算环境中的力量是计算机科学的关键发现之一。这个项目研究基本问题的算法，将进一步探索和利用随机性提供的这种能力。考虑到这样一个基本问题的一个例子是设施位置：我们如何以低成本放置设施，以最大限度地减少客户的总通勤时间？这个经典问题也有重要的现代应用：例如，在机器学习的聚类数据中，以及在互联网云上放置服务。PI旨在通过新的概率技术解决如何最好地解决这一问题，以及与集群和设施位置密切相关的问题。PI还将通过随机算法研究优化中的其他此类基本问题（例如，有效资源分配），以及研究此类调查如何改进和/或开发广泛适用的概率技术。该项目旨在通过人力资源开发产生更广泛的影响。研究生将直接参与几乎所有拟议的研究。PI指导了两个多年的“宝石”本科研究团队，两个团队的研究成果都在国家级会议上发表。PI建议在2018年左右开始为一个新的这样的团队提供建议，并继续让他们接触算法、随机性和网络之间的相互作用。此外，PI将指导两名高中生；这些学生将继续学习算法、随机性和应用，从基础到前沿研究。其中一名高中生的研究在PI的共同指导下，被邀请参加2017年的英特尔国际科学与工程博览会。这个项目的很大一部分将通过（新技术）随机化来开发改进的近似算法：近似算法是那些被证明是有效的，并且在可证明的距离内提供最优解的算法。在这方面考虑的两个代表性问题示例是设施位置（打开给定设施集合的一个子集，以最小化设施打开成本和客户总通勤时间的总和，以及这个经典问题的变体），以及在一般设置中将工作分配给服务器，以最小化工作完成时间的总和（由工作的各个优先级加权）。在方法上，该项目建议开发新技术，通过随机化仔细地将不可行的解决方案“圆”为可行的解决方案，以进一步理解信息论概念的力量（例如，当一个人有一系列随机选择的概率分布选择时，选择熵最大化的分布是否能提供额外的力量？），以及线性代数和概率论证之间的相互作用。“四舍五入”方法是灵活和通用的：例如，对于设施选址和工作分配问题，计算上很容易从接近最优但不可行的解决方案开始，关键的开放性问题是如何最优四舍五入到可行的解决方案。这种舍入技术的进步对近似算法产生了许多影响；该项目的一个关键目标是促进进一步的这些进步。

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.