Skip to main content

Research Repository

Advanced Search

Round-competitive algorithms for uncertainty problems with parallel queries

Erlebach, Thomas; Hoffmann, Michael; de Lima, Murilo Santos

Round-competitive algorithms for uncertainty problems with parallel queries Thumbnail


Authors

Michael Hoffmann

Murilo Santos de Lima



Abstract

In computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the settings where queries are asked sequentially (adaptive model) or all at once (non-adaptive model). We introduce 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. Using competitive analysis, we present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds for the given instance. Given a set of uncertain elements and a family of m subsets of that set, we study the problems of sorting all m subsets and of determining the minimum value (or the minimum element(s)) of each subset. We also study the selection problem, i.e., the problem of determining the i-th smallest value and identifying all elements with that value in a given set of uncertain elements. Our results include 2-round-competitive algorithms for sorting and selection and an algorithm for the minimum value problem that uses at most (2 + ε) · optk + O 1 ε · lg m query rounds for every 0 < ε < 1, where optk is the optimal number of query rounds

Citation

Erlebach, T., Hoffmann, M., & de Lima, M. S. (2023). Round-competitive algorithms for uncertainty problems with parallel queries. Algorithmica, 85(2), 406-443. https://doi.org/10.1007/s00453-022-01035-6

Journal Article Type Article
Acceptance Date Aug 28, 2022
Online Publication Date Sep 15, 2022
Publication Date 2023-02
Deposit Date Aug 29, 2022
Publicly Available Date Mar 15, 2023
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 85
Issue 2
Pages 406-443
DOI https://doi.org/10.1007/s00453-022-01035-6

Files

Published Journal Article (667 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.






Downloadable Citations