Nov. 22, 2023, 1:07 p.m.
Mateusz Basiak and Agnieszka Tatarczuk have won the faculty competition for best master's theses in computer science.
The final event of the Faculty Competition for Best Diploma Theses will take place this Friday, November 24, in room 25 of the Institute of Computer Science, University of Wrocław. During the event, we will learn the results of the competition for bachelor's and engineering theses. The results of the competition for master's theses are already known. The first prize was awarded to Mateusz Basiak and Agnieszka Tatarczuk for the work On the Online Min-Sum Set Cover Problem. The supervisor was Marcin Bieńkowski.
Below is a brief, informal summary prepared by the authors.
The paper describes an algorithm for the problem named "Online Min-Sum Set Cover", which can be thought of in this way: We have a shelf full of books and a bookseller whose desk is located at the left edge of the shelf. Customers come to him, needing books on a particular topic (there are at most r books on one topic, a customer needs only one book, a book can have multiple topics). The bookseller knows well where these books are on the shelf but doesn't like to go far. Whenever he walks along the shelf, he can swap books in place. He also doesn't like to make book swaps; it costs him valuable energy gained from cookies and coffee at his desk. The goal of the algorithm is to design the bookseller's decisions on book swaps so that he uses as little energy as possible for any queue of customers.
In the formal definition of the problem, we replace the shelf with a sequence, books with "elements," and topics with sets of elements. The energy used by the bookseller is the cost of handling requests and changing permutations.
Our algorithm improves the best competitive ratio (indicating how many times worse it is than an algorithm that knows the future) among known polynomial deterministic algorithms.
The algorithm can be applied, for example, in the construction of tools for searching under incomplete information, such as search engines, e-commerce, or news aggregation. It has been published at Workshop on Approximation and Online Algorithms (WAOA) where it has been given Best paper award.
The prizes are sponsored by Allianz Quantitative Analytics.
