Abstract: We are given an unknown binary matrix, where the entries correspond to preferences of users on items. We want to find at least one 1-entry in each row with a minimum number of queries. The number of queries needed heavily depends on the input matrix and a straightforward competitive analysis yields bad results for any online algorithm. Therefore, we analyze our algorithm against a weaker offline algorithm that is given the number of users and a probability distribution according to which the preferences of the users are chosen.
Bio: Jara Uitto received his M.Sc. in 2011 from the Department of Computer Science at the University of Helsinki. He worked from 2009 as a research assistant in HIIT in the Adaptive Computing Research Group led by Docent Patrik Floréen and Petteri Nurmi. Since 2011, he is doing his doctoral studies in the Distributed Computing Group in ETH Zürich supervised by Dr. Prof. Roger Wattenhofer. His research interest include algorithms, distributed computing and graph theory.
Last updated on 4 Feb 2014 by Antti Ukkonen - Page created on 4 Feb 2014 by Antti Ukkonen