A stochastic analog to Chebyshev centers and optimal average case algorithms (Q1117550)

We study a stochastic analogue to Chebyshev centers in a metric space. We prove several statements concerning the existence and uniqueness of these centers. Similarly as in the worst case these results can be used to prove the existence and uniqueness of optimal average case algorithms. We also show that nonmeasurable algorithms are not better than measurable ones.