Back to search

Georgia Institute of Technology

Online Allocation with Concave and Convex Objectives

Abstract

dc:description.abstract

Online 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Patton, Kalen Rohan. Online Allocation with Concave and Convex Objectives. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82152