{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/53344"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/53344","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Efficient algorithms for online resource allocation and submodular maximization","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Spaeh, Fabian"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Ene, Alina"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-11-18T19:35:23Z","subjects":["Computer science","Approximation algorithms","Online algorithms","Optimization","Submodular optimization"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0003-4816-471X"],"render_values":[{"text":"0000-0003-4816-471X","href":"https://orcid.org/0000-0003-4816-471X","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/53344","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/53344","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F53344","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ene, Alina"]},{"key":"dc:creator","label":"Author","values":["Spaeh, Fabian"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0000-0003-4816-471X"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-07-17T17:10:19Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-07-17T17:10:19Z"]},{"key":"dc:date.issued","label":"Date","values":["2025"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2026-07-17T16:15:45Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Approximation algorithms","Online algorithms","Optimization","Submodular optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/53344"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["2025"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Efficient algorithms for online resource allocation and submodular maximization"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ene, Alina"],"dc:creator":["Spaeh, Fabian"],"dc:date.accessioned":["2026-07-17T17:10:19Z"],"dc:date.available":["2026-07-17T17:10:19Z"],"dc:date.issued":["2025"],"dc:date.updated":["2026-07-17T16:15:45Z"],"dc:description":["2025"],"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."],"dc:identifier.orcid":["0000-0003-4816-471X"],"dc:identifier.uri":["https://hdl.handle.net/2144/53344"],"dc:language.iso":["en_US"],"dc:subject":["Computer science","Approximation algorithms","Online algorithms","Optimization","Submodular optimization"],"dc:title":["Efficient algorithms for online resource allocation and submodular maximization"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T19:35:23Z"}