University of Leicester
Browse

Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries

Download (750.06 kB)
conference contribution
posted on 2021-02-15, 09:57 authored by Thomas Erlebach, Michael Hoffmann, Murilo S de Lima
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 +ε)·optk+ O1ε·lgm?rounds for every0< ε <1, where optk is the optimal number of rounds, as well as nearly matching lower bounds. For the problem of determining thei-th smallest value and identifying all elements with that value in a set of uncertain elements, we give a2-round-competitivealgorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a2-round-competitive algorithm and this is the best possible.

History

Author affiliation

School of Informatics

Source

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

Version

  • VoR (Version of Record)

Published in

LIPIcs : Leibniz International Proceedings in Informatics

Pagination

13:1 - 13:18

Publisher

Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

issn

1868-8969

Acceptance date

2020-12-20

Copyright date

2021

Spatial coverage

Saarbrücken (Germany)

Temporal coverage: start date

2021-03-16

Temporal coverage: end date

2021-03-19

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC