Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
复制标题
DOI：
10.1007/s00453-022-01035-6
复制
发表时间：
2021-01
期刊：
影响因子：
1.1
通讯作者：
T. Erlebach;Michael Hoffmann;Murilo Santos de Lima
中科院分区：
文献类型：
--
作者：
T. Erlebach;Michael Hoffmann;Murilo Santos de Lima
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 wherekqueries 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 ofmsubsets of that set, we study the problems of sorting allmsubsets 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 thei-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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2+\varepsilon ) \cdot \mathrm {opt}_k+\mathrm {O}\left( \frac{1}{\varepsilon } \cdot \lg m\right) $$\end{document} query rounds for every, whereis the optimal number of query rounds.
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 wherekqueries 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 ofmsubsets of that set, we study the problems of sorting allmsubsets 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 thei-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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2+\varepsilon ) \cdot \mathrm {opt}_k+\mathrm {O}\left( \frac{1}{\varepsilon } \cdot \lg m\right) $$\end{document} query rounds for every, whereis the optimal number of query rounds.