22 listopada 2023 13:07
Mateusz Basiak i Agnieszka Tatarczuk wygrywają wydziałowy konkurs prac magisterskich z informatyki
Finał wydziałowego konkursu prac dyplomowych już w najbliższy piątek 24 listopada w sali 25 II UWr. W jego czasie poznamy wyniki konkursu prac licencjackich i inżynierskich. Wyniki konkursu prac magisterskich są już znane. Pierwszą nagrodę zdobyli Mateusz Basiak i Agnieszka Tatarczuk za pracę On the Online Min-Sum Set Cover Problem. Promotorem był Marcin Bieńkowski.
Poniżej krótkie, nieformalne streszczenie przygotowane przez autorów.
Praca opisuje algorytm dla problemu o wdzięcznej nazwie Online Min-Sum Set Cover, o którym można myśleć następująco: Mamy półkę pełną książek i księgarza, którego biurko znajduje się przy lewej krawędzi półki. Przychodzą do niego petenci, potrzebujący książek na jakiś temat (książek na jeden temat zawsze jest co najwyżej r, petent potrzebuje tylko jednej książki, książka może mieć wiele tematyk w sobie). Księgarz dobrze wie, gdzie są te książki na półce, ale nie lubi iść daleko. Zawsze, gdy idzie się przejść wzdłuż półki może zamieniać książki miejscami. Zamiany książek też nie lubi robić, kosztuje to cenną energię zdobytą na ciastku i kawie przy biurku. Celem algorytmu jest tak zaprojektować decyzje księgarza o zamianach książek, żeby dla dowolnej kolejki petentów zużył możliwie mało energii.
W formalnej definicji problemu półkę zastępujemy ciągiem, książki ,,elementami'', a tematy zbiorami elementów. Energia zużywana przez księgarza to koszt obsługi żądań i zmian permutacji.
Nasz algorytm poprawia najlepszy współczynnik konkurencyjności (oznaczający ile razy jest gorszy od algorytmu znającego przyszłość) spośród znanych wielomianowych deterministycznych algorytmów.
Algorytm Mateusza i Agnieszki może być zastosowany np. przy budowie narzędzi do wyszukiwania w sytuacjach niepełnej informacji np. wyszukiwarki internetowe, e-commerce czy agregacja newsów. Został opublikowany we wspólnej pracy z promotorem na Workshop on Approximation and Online Algorithms (WAOA), gdzie otrzymał Best paper award.
Sponsorem konkursu i fundatorem nagród była firma Allianz Quantitative Analytics.
