Back to search

Boston University

Efficient algorithms for online resource allocation and submodular maximization

Abstract

dc:description.abstract

In this thesis, we develop efficient algorithms for fundamental optimization problems in online allocation and submodular maximization. We focus on algorithms that obtain strong theoretical guarantees without sacrificing practicality. We design algorithms with improved approximation guarantees and fast end-to-end running time. Our algorithms for the online and streaming setting additionally use few function evaluations and low memory. First, we study online ad allocation and the online generalized assignment problem, which are motivated by applications such as digital advertising. To improve beyond known lower bounds, our novel algorithm leverages predictions while maintaining robustness against inaccurate predictions. Our method generalizes prior work and demonstrates strong practical results on both synthetic and real-world datasets. In Chapter 2, we extend our prediction framework to the more general problem of whole-page optimization, which requires choosing from configurations of advertisers. Next, we consider k-submodular maximization in the online setting. k-Submodular objectives generalize the linear objectives of the preceding chapters and model problems such as ad allocation and personalized recommendation. We develop a versatile online algorithmic framework allowing us to address many challenging settings in which we improve upon the best known approximation guarantee. Our algorithms are also computationally efficient and require low memory, which makes them suited for the streaming setting. Finally, we turn to the offline setting where we investigate influence maximization, commonly addressed using methods from submodular maximization. Drawing upon techniques from low-adaptivity submodular maximization, we introduce randomized optimization procedures that improve the sample complexity and running time compared to prior work. We confirm the practical benefits over prior work via an empirical evaluation.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor
Boston University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Spaeh, Fabian
Advisor dc:contributor.advisor
  • Ene, Alina
ORCID dc:identifier.orcid

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53344

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Spaeh, Fabian. Efficient algorithms for online resource allocation and submodular maximization. doctoral thesis, Boston University, 2025. https://hdl.handle.net/2144/53344