Round-competitive algorithms for uncertainty problems with parallel queries

DOI10.1007/S00453-022-01035-6MaRDI QIDQ2684483zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.05032

zbMATH Keywords

competitive analysisexplorable uncertaintyminimum problemonline algorithmsparallel algorithmsselection problemsorting problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Online algorithms; streaming algorithms (68W27)

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+varepsilon)cdotmathrm{opt}_k+mathrmOleft(frac1varepsiloncdotlgmight)$ rounds for every $0<varepsilon<1$, where $mathrm{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.

Recommendations

• scientific article; zbMATH DE number 7075885
• Algorithms for queryable uncertainty
• Query-competitive sorting with uncertainty
• Query-Competitive Sorting with Uncertainty.
• Computing and scheduling with explorable uncertainty

Cites work

• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An adaptivity hierarchy theorem for property testing
• An adversarial model for scheduling with testing
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Explorable uncertainty in scheduling with non-uniform testing times
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• Inequalities on the Lambert W function and hyperpower function
• Information collection for linear programs with uncertain objective coefficients
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Minimum spanning tree verification under uncertainty
• Noisy sorting without resampling
• Preprocessing Ambiguous Imprecise Points
• Query-competitive algorithms for cheapest set problems under uncertainty
• Query-Competitive Sorting with Uncertainty.
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Representation of a finite graph by a set of intervals on the real line
• Stochastic packing integer programs with few queries
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• The robust knapsack problem with queries
• The update complexity of selection and related problems
• Verification problem of maximal points under uncertainty

Cited in

(13)

• Computing and scheduling with explorable uncertainty
• Query-competitive sorting with uncertainty
• The update complexity of selection and related problems
• The update complexity of selection and related problems
• scientific article; zbMATH DE number 1560893 (Why is no real title available?)
• Algorithms for queryable uncertainty
• Computing the Median with Uncertainty
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• Query-Competitive Sorting with Uncertainty.
• Query minimization under stochastic uncertainty
• Greediness is not always a vice: efficient discovery algorithms for assignment problems
• Reachability in temporal graphs under perturbation
• Algorithms that access the input via queries

This page was built for publication: Round-competitive algorithms for uncertainty problems with parallel queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684483)