EAGER: Probabilistic Models and Algorithms

EAGER：概率模型和算法

• 批准号: 1749864
• 负责人: Aravind Srinivasan
• 金额: $ 12.9万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-15 至 2020-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1749864&HistoricalAwards=false
• 关键词: EAGER; Probabilistic; Models; 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.

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

项目成果

A Randomized Approximation Technique for Resource-Allocation Problems

资源分配问题的随机逼近技术

• 发表时间: 2018
• 期刊: Random structures & algorithms
• 影响因子: 1
• 作者: Saha, Barna;Srinivasan, Aravind
• 通讯作者: Srinivasan, Aravind

Algorithms to Approximate Column-sparse Packing Problems

• DOI: 10.1145/3355400
• 发表时间: 2017-11
• 期刊: ACM Transactions on Algorithms (TALG)
• 作者: Brian Brubach;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu

Hierarchical Scheduling Algorithms with Throughput Guarantees and Low Delay

保证吞吐量、低延迟的分层调度算法

• 发表时间: 2018
• 期刊: Ad Hoc and Wireless Networks (WiOpt
• 作者: Swamy, Peruru S;Srinivasan, Aravind;Ganti, Radha K;Jagannathan, Krishna
• 通讯作者: Jagannathan, Krishna

Allocation Problems in Ride Sharing Platforms: Online Matching with Offline Reusable Resources

乘车共享平台的分配问题：线上匹配线下可复用资源

• 发表时间: 2018
• 期刊: Proc. Thirty-Second AAAI Conference on Artificial Intelligence (AAAI
• 作者: Dickerson, John P.;Sankararaman, Karthik A.;Srinivasan, Aravind;Xu, Pan
• 通讯作者: Xu, Pan

Improved Bounds in Stochastic Matching and Optimization

• DOI: 10.1007/s00453-017-0383-4
• 发表时间: 2017-10
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Alok Baveja;Amit Chavan;Andrei Nikiforov;A. Srinivasan;Pan Xu