Title: Online Resource Allocation and Load Balancing with Norms
Date: Thursday, October 3, 2024
Time: 12:00pm - 1:00pm
Location: Klaus 3100
Kalen Patton
School of Mathematics
College of Science
Georgia Institute of Technology
Committee
Sahil Singla (advisor) - School of Computer Science, Georgia Institute of Technology
Mohit Singh - School of Industrial and Systems Engineering, Georgia Institute of Technology
Santosh Vempala - School of Computer Science, Georgia Institute of Technology
Cheng Mao - School of Mathematics, Georgia Institiute of Technology
Abstract
In economics, theoretical computer science, and operations research, many central problems involve resource allocation and load balancing. Online resource allocation problems model situations in which a series of requests arrives online, and each request must be immediately and irrevocably allocated to one of several offline agents. Each allocation incurs an associated a cost and reward, and the goal is to maximize the reward obtained subject to some budget constraints on the costs. On the other hand, online load balancing problems are a closely related minimization variant, in which our goal is to simply allocate all requests while minimizing the incurred cost.
Recently, these problems have gained attention in a generalized setting, in which the vector of costs incurred over agents is aggregated with an arbitrary monotone norm. While competitive algorithms are known for certain classes of norms, the question of which norms admit such algorithms remains largely open. In this talk, we will discuss recent work in this area, our contributions, and remaining open questions. If time permits, we will also briefly discuss another direction of research on online resource allocation with correlated inputs.
