AF: Small: Allocation Algorithms in Online Systems

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

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.