Title: Online Allocation with Concave and Convex Objectives
Kalen Patton
Ph.D. Candidate
Algorithms, Combinatorics, and Optimization
School of Mathematics
Date: Thursday May 7, 2026
Time: 01:00pm EDT
Location: Klaus 1116 Seminar Room
Committee
Dr. Sahil Singla, Advisor, School of Computer Science, Georgia Institute of Technology
Dr. Mohit Singh, Reader, School of Industrial & Systems Engineering, Georgia Institute of Technology
Dr. Cheng Mao, School of Mathematics, Georgia Institute of Technology
Dr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology
Draft of Thesis: https://sites.gatech.edu/kpatton33/thesis
Abstract
Online allocation problems model scenarios in which an unknown sequence of requests arrives one at a time, and each request must be immediately satisfied upon arrival by assigning it to one of m agents. The goal for such problems is to find an allocation to optimize some objective such as minimizing cost or maximizing welfare. Such problems arise frequently in real-world settings where decisions must be made without knowledge of the future, including cloud computing (allocating incoming jobs to servers), online advertising (allocating ad slots on a webpage among advertisers) and humanitarian aid (allocating finite relief resources as needs arise).
In practice, the objectives we seek to optimize may be complex to account for problem-specific notions of utility and fairness, so a natural aim of online optimization research is to design flexible algorithms which can perform well in a wide range of settings. Foundational work on online allocation problems often establishes algorithms which are provably good approximations of the optimal assignment in hindsight, but only for certain well-structured settings. More recent work over the last two decades has begun to extend such algorithms beyond classical problems, but such extensions are often limited in scope and involve problem-specific techniques, leading to a patchwork understanding of such problems. In this thesis, we seek to develop a more comprehensive theory of online allocation problems, motivated by the following overarching question:
Can we design general-purpose algorithms for online allocation problems that are approximately optimal across many applications?
We examine this question in two main areas: maximization problems with concave objectives (e.g., online bipartite matching, resource allocation and welfare) and minimization problems with convex objectives (e.g., load balancing, scheduling and covering problems). For maximization problems, we develop new primal-dual tools for fractional matching and resource allocation which allow unified algorithms for many previously disjoint settings. For minimization problems, we develop new methods for optimizing various convex and norm objectives, leveraging key structural properties of such functions to obtain new results for problems such as load balancing, set cover, and facility location.
