AF: Small: Allocation Algorithms in Online Systems

AF：小型：在线系统中的分配算法

• 批准号: 1527084
• 负责人: Debmalya Panigrahi
• 金额: $ 41.6万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527084&HistoricalAwards=false
• 关键词: AF; Small; Allocation; Algorithms; Online

In recent years, the Internet has undergone explosive growth --- in the number of users and connected devices, volume of traffic, geographical reach, and diversity of services --- and its role in enriching modern human societies is indisputable. Two key contributors to this growth and success are: (a) the unique economic model of the Internet that predominantly relies on advertising revenues instead of paid services thereby allowing multitudes of users affordable access to online services such as email and search, and connectivity via social networks; and (b) the large-scale computing infrastructure based on massive data centers capable of providing computing and connectivity services to billions of users across the globe at any given time. The success of these critical components of the Internet revolution is contingent on the development of efficient allocation algorithms --- for deciding which advertisement an ad exchange should show an online user to maximize the user's utility and generate revenue, and for scheduling user service requests on the available resources such as processors, storage devices, and network elements in a data center. In this project, the PI will develop novel algorithmic tools and techniques to address these problems, thereby advancing the state of the art in algorithmic research. Moreover, the PI will regularly consult with practitioners to create opportunities for technology transfer in Internet applications. This project will also train graduate and undergraduate researchers in algorithms and theoretical computer science, with a focus on problems motivated by real world applications.Allocation problems in large online systems have emerged as a vibrant area of research. In this project, the focus is on two important domains: scheduling and load balancing with applications to data center management, and online matching and budgeted allocation with applications to Internet advertising. Both application domains have been at the forefront of the Internet revolution and have grown into multi-billion dollar industries. Moreover, from a technical perspective, these problems are characterized by some of the key challenges in modern algorithm design for real world problems: uncertainty and incompleteness of input data, the existence of multiple simultaneous objectives, and non-linear optimization requirements. This project will address technical problems in the above-mentioned application domains that exhibit one or more of these characteristics. Specific problems to be considered include vector scheduling and load balancing, online convex optimization and applications to non-linear scheduling objectives, multi-objective and stochastic versions of budgeted allocation and online matching problems, etc. The successful completion of this project will yield an algorithmic toolkit for allocation problems motivated by real world applications on the Internet.

近年来，互联网经历了爆炸性的增长 - 在用户和连接的设备数量，交通量，地理覆盖范围和服务的多样性中 - 及其在丰富现代人类社会中的作用是无关的。这一增长和成功的两个关键因素是：（a）互联网的独特经济模型，主要依赖广告收入，而不是付费服务，从而允许许多用户负担得起的在线服务（例如电子邮件和搜索）以及通过社交网络的连通性访问； （b）基于能够在任何给定时间为全球数十亿用户提供计算和连接服务的大规模计算基础架构。互联网革命的这些关键组成部分的成功取决于有效分配算法的开发 - - 确定广告交易所应显示在线用户最大化用户的实用程序并生成收入，并在可用资源上安排用户服务请求，例如处理器，存储设备以及数据中心中的网络元素。在这个项目中，PI将开发新颖的算法工具和技术来解决这些问题，从而在算法研究中提高最新技术。此外，PI将定期咨询从业人员，以创造互联网应用程序中技术转移的机会。该项目还将在算法和理论计算机科学领域培训研究生和本科研究人员，重点是由现实世界应用所激发的问题。大型在线系统的分配问题已成为一个充满活力的研究领域。在这个项目中，重点是两个重要领域：调度和负载平衡与数据中心管理的应用程序，以及在线匹配和预算分配以及应用于Internet广告的应用程序。这两个应用领域都处于互联网革命的最前沿，并已发展为数十亿美元的行业。此外，从技术角度来看，这些问题的特征是现代算法设计中针对现实世界中问题的一些关键挑战：输入数据的不确定性和不完整，存在多个同时目标以及非线性优化要求。该项目将解决上述应用领域中表现出一个或多个特征的技术问题。要考虑的特定问题包括矢量调度和负载平衡，在线凸优化以及针对非线性调度目标的应用程序，预算分配和在线匹配问题的多目标和随机版本等。该项目的成功完成将产生一个算法工具包，以实现现实世界应用程序激励的分配问题。