AF: Small: Allocation Algorithms in Online Systems

点击翻译按钮获取中文摘要

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.