Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$.  We do not have access to the values of these elements, but we can compare any two elements of $S$ to see which one is smaller.  For any indices $i$ and $j$, there is an associated cost $C_{i,j}$ to compare the $i$th and $j$th elements of $S$.  The complete cost matrix $C_{i,j}$ is given to us in advance.It is well known that $n-1$ comparisons are necessary and sufficient to find the smallest element of $S$.  However, since each comparison may have a different cost, we also want to keep the total cost of the comparisons as small as possible. Is there an online algorithm that finds a sequence of comparisons of small total cost that finds the smallest element of $S$?  There is no online algorithm that finds the set of comparisons with minimum total cost, even when $n=3$, but perhaps there is an online algorithm with small competitive ratio.  In particular, does allowing the online algorithm to perform more than $n-1$ comparisons help?  Is it better to make several extra cheap comparisons instead of a few expensive comparisons?I am especially interested in the case $C_{i,j} = 4^{d(i,j)}$, where $d$ is a discrete metric over the set $S$, and $0 \le d(i,j) \le k$, for all $i,j$.  An optimal online algorithm is still impossible in this setting.Any references to similar problems are appreciated. I'm not searching for someone to solve my problem (although some ideas may help and are appreciated).  I just want to know if this problem is known. (I couldn't find anything.) 
Cheap online selection with weighted comparisons
cc.complexity theory;ds.algorithms;reference request;online algorithms