Sequential Utilitarian Combinatorial Assignment: Extending Static Allocation Algorithm with Sequential Execution Framework
2025 (Engelska)Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hp
Studentuppsats (Examensarbete)
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
Ort, förlag, år, upplaga, sidor
2025. , s. 34
Nyckelord [en]
combinatorial assignment problem, task scheduling, dynamic environments, sequential framework, resource allocation optimization, utility maximization
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:liu:diva-215875ISRN: LIU-IDA/LITH-EX-A--25/081--SEOAI: oai:DiVA.org:liu-215875DiVA, id: diva2:1980209
Ämne / kurs
Datavetenskap
Presentation
2025-06-19, Alan Turing, Olaus Magnus Väg, 583 30, Linköping, 10:00 (Engelska)
Handledare
Examinatorer
2025-07-012025-07-012025-07-01Bibliografiskt granskad