liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Sequential Utilitarian Combinatorial Assignment: Extending Static Allocation Algorithm with Sequential Execution Framework
Linköpings universitet, Institutionen för datavetenskap.
2025 (Engelska)Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (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
Tillgänglig från: 2025-07-01 Skapad: 2025-07-01 Senast uppdaterad: 2025-07-01Bibliografiskt granskad

Open Access i DiVA

bilaga(2993 kB)251 nedladdningar
Filinformation
Filnamn ATTACHMENT01.pdfFilstorlek 2993 kBChecksumma SHA-512
d546300d3e96f09a79c32ddd9881d4c8791bb490ef46d32729b76783ed7dbc835c859f61b925b6bece5ec347347559237096c68834574c8fef0b64185c037d90
Typ attachmentMimetyp application/pdf

Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 321 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf