Abstract
dc:description.abstractOnline allocation refers to the problem of allocating a unknown sequence of arriving items to agents in order to maximize or minimize some objective. Such problems fall into the broad field of optimization under uncertainty, as each item must be allocated immediately without knowledge of future arrivals. In this thesis, we seek to develop unified algorithms and methods for online allocation problems which can account for a wider variety of objectives and problem settings. The results of this thesis are presented in two parts: In Part I, we examine online maximization problems, including matching and resource allocation, while in Part II, we examine online minimization problems, including load balancing, facility location, and set cover. 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.
Degree
thesis:*- Name thesis:degree_name
- Algorithms, Combinatorics, and Optimization, PhD
- Department thesis:degree_department
- Mathematics
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Patton, Kalen Rohan
- Advisor dc:contributor.advisor
-
- Singla, Sahil
- Committee members dc:contributor.committeemember
-
- Singh, Mohit
- Vempala, Santosh
- Mao, Cheng
- ORCID person:identifier.orcid
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82152