Cheap online selection with weighted comparisons 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.)
Brute-force case analysis reveals that the optimal competitive ratio for the special case  $n=3$, with no other restrictions on the cost matrix, is the golden ratio $\phi = (\sqrt{5}+1)/2$.  Thus, no online algorithm can achieve a competitive ratio better than $\phi$.

Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$.


Without loss of generality, the algorithm starts by comparing $S_1$ to $S_2$, at cost zero.
The adversary declares $S_1 &gt; S_2$.
If the algorithm compares $S_1$ to $S_3$:


The adversary declares $S_1 &gt; S_3$.
The algorithm must compare $S_2$ and $S_3$.
The adversary declares $S_2 &lt; S_3$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $1+\phi$.
The adversary reveals the total order $S_2 &lt; S_3 &lt; S_1$.
The total cost of the optimal comparisons ($S_1&gt;S_2$ and $S_2&lt;S_3$) is $\phi$.

If the algorithm compares $S_2$ to $S_3$:


The adversary declares $S_3 &gt; S_2$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $\phi$.
The adversary reveals the total order $S_2 &lt; S_1 &lt; S_3$.
The total cost of the optimal comparisons ($S_1&gt;S_2$ and $S_1&lt;S_3$) is $1$.

In either case, the algorithm's comparisons cost a factor of $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$ more than the optimal set of comparisons for the revealed total order.


More generally, the competitive ratio is $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$, where $a\le b\le c$ are the three comparison costs.  (There are more cases to consider here, because there are optimal algorithms that do not perform the cheapest comparison first, but the case analysis is still elementary.)  Tedious calculations imply that the expression $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ is maximized when $a=0$, $b=1$, and $c=\phi$.

In particular, if $\frac{a+c}{a+b} &gt; \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.