liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sequential Utilitarian Combinatorial Assignment: Extending Static Allocation Algorithm with Sequential Execution Framework
Linköping University, Department of Computer and Information Science.
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent 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
Available from: 2025-07-01 Created: 2025-07-01 Last updated: 2025-07-01Bibliographically approved

Open Access in DiVA

bilaga(2993 kB)240 downloads
File information
File name ATTACHMENT01.pdfFile size 2993 kBChecksum SHA-512
d546300d3e96f09a79c32ddd9881d4c8791bb490ef46d32729b76783ed7dbc835c859f61b925b6bece5ec347347559237096c68834574c8fef0b64185c037d90
Type attachmentMimetype application/pdf

By organisation
Department of Computer and Information Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 317 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf