Boston University
Efficient algorithms for online resource allocation and submodular maximization
Abstract
dc:description.abstractIn 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 × 5Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53344