Query-Competitive Sorting with Uncertainty.

DOI10.4230/LIPIcs.MFCS.2019.7OpenAlexW3145083791MaRDI QIDQ5092365

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

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.7

zbMATH Keywords

sortingonline algorithmsrandomized algorithmsadvice complexitythreshold tolerance graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Set selection under explorable stochastic uncertainty via covering techniques ⋮ Round-competitive algorithms for uncertainty problems with parallel queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• The update complexity of selection and related problems
• The robust knapsack problem with queries
• Efficient update strategies for geometric computing with uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty
• Robust optimization - a comprehensive survey
• Verification Problem of Maximal Points under Uncertainty
• Introduction to Stochastic Programming
• Computing shortest paths with uncertainty
• Sorting and Selection with Imprecise Comparisons
• Threshold tolerance graphs
• Computing the Median with Uncertainty
• Information Collection for Linear Programs with Uncertain Objective Coefficients
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Quicksort

This page was built for publication: Query-Competitive Sorting with Uncertainty.