Erlebach, Thomas ;
Hoffmann, Michael ;
de Lima, Murilo Santos
RoundCompetitive Algorithms for Uncertainty Problems with Parallel Queries
Abstract
The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of the weight of an element, we may be given an interval that is guaranteed to contain the weight, and a query can be performed to reveal the weight. While previous work has considered models where queries are asked either sequentially (adaptive model) or all at once (nonadaptive model), and the goal is to minimize the number of queries that are needed to solve the given problem, we propose and study a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. We use competitive analysis and present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds. Given a set of uncertain elements and a family of m subsets of that set, we present an algorithm for determining the value of the minimum of each of the subsets that requires at most (2+ε) ⋅ opt_k+O(1/(ε) ⋅ lg m) rounds for every 0 < ε < 1, where opt_k is the optimal number of rounds, as well as nearly matching lower bounds. For the problem of determining the ith smallest value and identifying all elements with that value in a set of uncertain elements, we give a 2roundcompetitive algorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a 2roundcompetitive algorithm and this is the best possible.
BibTeX  Entry
@InProceedings{erlebach_et_al:LIPIcs.STACS.2021.27,
author = {Erlebach, Thomas and Hoffmann, Michael and de Lima, Murilo Santos},
title = {{RoundCompetitive Algorithms for Uncertainty Problems with Parallel Queries}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {27:127:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13672},
URN = {urn:nbn:de:0030drops136728},
doi = {10.4230/LIPIcs.STACS.2021.27},
annote = {Keywords: online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem}
}
10.03.2021
Keywords: 

online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem 
Seminar: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Issue date: 

2021 
Date of publication: 

10.03.2021 