Sequential Utilitarian Combinatorial Assignment: Extending Static Allocation Algorithm with Sequential Execution Framework
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
Student thesis
Abstract [en]
Combinatorial assignment problems involving finite resource allocation have traditionally been studied in static, single-instance settings. This thesis introduces SEQUCA, a sequential framework that extends a state-of-the-art Utilitarian Combinatorial Assignment (UCA) algorithm to dynamic environments. The framework evaluates social welfare across simulated time steps, accommodating stochastic task generation and fluctuating agent availability. Two implementations are compared: a baseline model that reapplies the UCA algorithm at each step, and a greedy extension that caches and reuses prior results when applicable. The results show that the greedy extension achieves comparable utility, with only minor reductions, while significantly improving execution time. Furthermore, the study identifies a performance bottleneck in the UCA algorithm when utility values across coalitions are identical, which reduces pruning effectiveness
Place, publisher, year, edition, pages
2025. , p. 34
Keywords [en]
combinatorial assignment problem, task scheduling, dynamic environments, sequential framework, resource allocation optimization, utility maximization
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-215875ISRN: LIU-IDA/LITH-EX-A--25/081--SEOAI: oai:DiVA.org:liu-215875DiVA, id: diva2:1980209
Subject / course
Computer science
Presentation
2025-06-19, Alan Turing, Olaus Magnus Väg, 583 30, Linköping, 10:00 (English)
Supervisors
Examiners
2025-07-012025-07-012025-07-01Bibliographically approved