License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.27
URN: urn:nbn:de:0030-drops-136728
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13672/
Erlebach, Thomas ;
Hoffmann, Michael ;
de Lima, Murilo Santos
Round-Competitive 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 (non-adaptive 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 i-th smallest value and identifying all elements with that value in a set of uncertain elements, we give a 2-round-competitive algorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a 2-round-competitive 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 = {{Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {27:1--27:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13672},
URN = {urn:nbn:de:0030-drops-136728},
doi = {10.4230/LIPIcs.STACS.2021.27},
annote = {Keywords: online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem}
}
|
Keywords: |
|
online algorithms, competitive analysis, explorable uncertainty, parallel algorithms, minimum problem, selection problem |
|
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
10.03.2021 |
