Computing the Median with Uncertainty

DOI10.1137/S0097539701395668zbMath1029.68161OpenAlexW1966156872MaRDI QIDQ4706217

Chris Olston, Rina Panigrahy, Jennifer Widom, Tomás Feder, Rajeev Motwani

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701395668

zbMATH Keywords

uncertaintyselectiononline algorithmsmedianquery processing

Mathematics Subject Classification ID

Theory of data (68P99) Approximation algorithms (68W25)

Related Items (19)

Scheduling with testing on multiple identical parallel machines ⋮ Randomization Helps Computing a Minimum Spanning Tree under Uncertainty ⋮ The update complexity of selection and related problems ⋮ The robust knapsack problem with queries ⋮ Query-competitive sorting with uncertainty ⋮ Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments ⋮ Unnamed Item ⋮ Set selection under explorable stochastic uncertainty via covering techniques ⋮ Round-competitive algorithms for uncertainty problems with parallel queries ⋮ Query-competitive algorithms for cheapest set problems under uncertainty ⋮ An adversarial model for scheduling with testing ⋮ Algorithms for Queryable Uncertainty ⋮ A robust optimization approach with probe-able uncertainty ⋮ Query minimization under stochastic uncertainty ⋮ Optimal path discovery problem with homogeneous knowledge ⋮ Query-Competitive Sorting with Uncertainty. ⋮ The Minimum Cost Query Problem on Matroids with Uncertainty Areas. ⋮ Randomization Helps Computing a Minimum Spanning Tree under Uncertainty ⋮ Explorable uncertainty in scheduling with non-uniform testing times

This page was built for publication: Computing the Median with Uncertainty