From arXiv cs daily comes a very interesting paper titled Online Medians via Online Bribery by Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young. Here is part of the abstract:
Our proofs reduce online medians to the following online bribery problem: faced with some unknown threshold T>0, an algorithm must submit “bids” b>0 until it submits a bid as large as T. The algorithm pays the sum of its bids. We describe optimally competitive algorithms for online bribery.
I suppose this can be a useful skill when I travel to some parts of the world later this summer? 
Full information:
Paper: cs.DS/0504103
Date: Wed, 27 Apr 2005 00:07:32 GMT (58kb)
Title: Online Medians via Online Bribery
Authors: Marek Chrobak and Claire Kenyon and John Noga and Neal E. Young
Comments: extended abstract
Subj-class: Data Structures and Algorithms
ACM-class: G.1.6; G.2.2; F.2.2
\
Following Mettu and Plaxton, we study online algorithms for the k-medians
problem. Such an algorithm must produce a nested sequence F_1\subseteq
F_2\subseteq…\subseteq F_n of sets of facilities. Mettu and Plaxton show that
online metric medians has a (roughly) 40-competitive deterministic
polynomial-time algorithm. We give improved algorithms, including a
(24+\epsilon)-competitive deterministic polynomial-time algorithm and a
5.44-competitive, randomized, non-polynomial-time algorithm.
We also consider the competitive ratio with respect to size. An algorithm is
s-size-competitive} if, for each k, the cost of F_k is at most the minimum cost
of any set of k facilities, while the size of F_k is at most s k. We present
optimally competitive algorithms for this problem.
Our proofs reduce online medians to the following online bribery problem:
faced with some unknown threshold T>0, an algorithm must submit “bids” b>0
until it submits a bid as large as T. The algorithm pays the sum of its bids.
We describe optimally competitive algorithms for online bribery.
Our results on cost-competitive online medians extend to approximately metric
distance functions, online fractional medians, and online bicriteria
approximation.
\ ( http://arXiv.org/abs/cs/0504103 , 58kb)
