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