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将开发新的算法工具和技术来解决这些问题，从而推进算法研究的最新发展。此外，首席信息官将定期与从业人员协商，为互联网应用技术转让创造机会。该项目还将培训算法和理论计算机科学方面的研究生和本科生研究人员，重点关注由真实的应用驱动的问题。大型在线系统中的分配问题已成为一个充满活力的研究领域。在这个项目中，重点是两个重要的领域：调度和负载平衡与应用程序的数据中心管理，在线匹配和预算分配与应用程序的互联网广告。这两个应用领域一直处于互联网革命的最前沿，并已发展成为数十亿美元的产业。此外，从技术的角度来看，这些问题的特点是在真实的世界问题的现代算法设计的一些关键挑战：输入数据的不确定性和不完整性，存在多个同时的目标，和非线性优化要求。本项目将解决上述应用领域中表现出一个或多个这些特征的技术问题。需要考虑的具体问题包括向量调度和负载平衡、在线凸优化及其在非线性调度目标中的应用、预算分配的多目标和随机版本以及在线匹配问题等。该项目的成功完成将产生一个算法工具包，用于解决互联网上真实的世界应用所激发的分配问题。