Query-competitive sorting with uncertainty

DOI10.1016/J.TCS.2021.03.021MaRDI QIDQ2663045zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Murilo S. de Lima

Publication date 15 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.09475, https://drops.dagstuhl.de/opus/volltexte/2019/10951/

zbMATH Keywords

online algorithmsrandomized algorithmsadvice complexitysortingthreshold tolerance graphs

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Searching and sorting (68P10)

Abstract: We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of $n$ data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries. We show that an offline optimum query set can be found in poly time, and that both oblivious and adaptive problems have simple competitive algorithms. The competitive ratio for the oblivious problem is $n$ for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2. We present a unified adaptive strategy for uniform costs that yields the following improved results: (1) a 3/2-competitive randomized algorithm; (2) a 5/3-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has competitive ratio $3/2+mathrmO(1/k)$ if the components obtained have size at least $k$; and (3) an exact algorithm for laminar families of intervals. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components. We also give a randomized adaptive algorithm with competitive ratio $1+frac43sqrt3approx1.7698$ for arbitrary query costs, and we show that the 2-competitive deterministic adaptive algorithm can be generalized for queries returning intervals and for a more general vertex cover problem, by using the local ratio technique. Moreover, we prove that the advice complexity of the adaptive problem is $lfloorn/2floor$ if no error threshold is allowed, and $lceiln/3cdotlg3ceil$ for the general case. Finally, we present some graph-theoretical results on co-threshold tolerance graphs, and we discuss uncertainty variants of some classical interval problems.

Recommendations

• Query-Competitive Sorting with Uncertainty.
• Query minimization under stochastic uncertainty
• Query minimization under stochastic uncertainty
• Round-competitive algorithms for uncertainty problems with parallel queries
• On sorting in the presence of erroneous information

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• A Mathematical Theory of Communication
• A linear-time approximation algorithm for the weighted vertex cover problem
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An adversarial model for scheduling with testing
• Co-TT graphs and a characterization of split co-TT graphs
• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• Information collection for linear programs with uncertain objective coefficients
• Introduction to stochastic programming.
• Minimum spanning tree under explorable uncertainty in theory and experiments
• Minimum spanning tree verification under uncertainty
• On recognition of threshold tolerance graphs and their complements
• Query-competitive algorithms for cheapest set problems under uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Representation of a finite graph by a set of intervals on the real line
• Robust optimization - a comprehensive survey
• Stochastic packing integer programs with few queries
• The robust knapsack problem with queries
• The update complexity of selection and related problems
• Threshold tolerance graphs
• Tolerance graphs
• Verification problem of maximal points under uncertainty

Cited in

(9)

• Query-Competitive Sorting with Uncertainty.
• Algorithms that access the input via queries
• Round-competitive algorithms for uncertainty problems with parallel queries
• Query minimization under stochastic uncertainty
• Two-stage robust optimization problems with two-stage uncertainty
• The power of amortization on scheduling with explorable uncertainty
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• Sorting under partial (interval order) information
• Query minimization under stochastic uncertainty

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Query-competitive sorting with uncertainty

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