Query-competitive sorting with uncertainty

DOI10.1016/J.TCS.2021.03.021zbMATH Open1462.68031arXiv2012.09475OpenAlexW3110806984MaRDI QIDQ2663045FDOQ2663045

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

Publication date: 15 April 2021

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

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.

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

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

zbMATH Keywords

online algorithmsrandomized algorithmsadvice complexitysortingthreshold tolerance graphs

Mathematics Subject Classification ID

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

Cites Work

• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Introduction to Stochastic Programming
• Representation of a finite graph by a set of intervals on the real line
• A linear-time approximation algorithm for the weighted vertex cover problem
• Robust optimization - a comprehensive survey
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The update complexity of selection and related problems
• Computing the Median with Uncertainty
• Title not available (Why is that?)
• Efficient update strategies for geometric computing with uncertainty
• The robust knapsack problem with queries
• Information Collection for Linear Programs with Uncertain Objective Coefficients
• Co-TT graphs and a characterization of split co-TT graphs
• On recognition of threshold tolerance graphs and their complements
• Threshold tolerance graphs
• Tolerance graphs
• Sorting and Selection with Imprecise Comparisons
• Computing shortest paths with uncertainty
• An adversarial model for scheduling with testing
• Title not available (Why is that?)
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty
• Verification Problem of Maximal Points under Uncertainty
• Title not available (Why is that?)
• Stochastic packing integer programs with few queries
• Minimum Spanning Tree Verification Under Uncertainty

Cited In (7)

• Algorithms that access the input via queries
• The power of amortization on scheduling with explorable uncertainty
• Query-Competitive Sorting with Uncertainty.
• Query minimization under stochastic uncertainty
• Round-competitive algorithms for uncertainty problems with parallel queries
• Title not available (Why is that?)
• Two-stage robust optimization problems with two-stage uncertainty

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)