<p>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$.  <strong>Thus, no online algorithm can achieve a competitive ratio better than $\phi$.</strong></p>

<p>Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$.</p>

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

<ul>
<li>The adversary declares $S_1 &gt; S_3$.</li>
<li>The algorithm must compare $S_2$ and $S_3$.</li>
<li>The adversary declares $S_2 &lt; S_3$, so $S_2$ is the minimum.</li>
<li>The total cost of the algorithm's comparisons is $1+\phi$.</li>
<li>The adversary reveals the total order $S_2 &lt; S_3 &lt; S_1$.</li>
<li>The total cost of the optimal comparisons ($S_1&gt;S_2$ and $S_2&lt;S_3$) is $\phi$.</li>
</ul></li>
<li><p>If the algorithm compares $S_2$ to $S_3$:</p>

<ul>
<li>The adversary declares $S_3 &gt; S_2$, so $S_2$ is the minimum.</li>
<li>The total cost of the algorithm's comparisons is $\phi$.</li>
<li>The adversary reveals the total order $S_2 &lt; S_1 &lt; S_3$.</li>
<li>The total cost of the optimal comparisons ($S_1&gt;S_2$ and $S_1&lt;S_3$) is $1$.</li>
</ul></li>
<li><p>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.</p></li>
</ul>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-08-11T11:30:44.227Z
That is a very good first step! Thanks for your interest in my problem (it seems that you are even more interested than me :) )
George
CC BY-SA 3.0
2012-08-11T18:10:29.290Z
Nice observation.  Just to note, this analysis assumes a deterministic algorithm unless I am mistaken.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-11T19:20:47.827Z
Yes, that's right.  A randomized algorithm might do better (in expectation, against an oblivious adversary).
Jeffε
CC BY-SA 3.0
2012-08-11T06:09:26.807Z
2012-08-11T06:09:26.807Z
Jeffε
<p>As a function of <span class="math-container">$n=|S|$</span>, the optimal competitive is <span class="math-container">$\Theta(n)$</span>:</p>
<p><strong>Lemma 1.</strong> <em>There is a deterministic <span class="math-container">$O(n)$</span>-competitive online algorithm.</em></p>
<p><strong>Lemma 2.</strong> <em>No deterministic (or randomized) online algorithm is <span class="math-container">$o(n)$</span>-competitive.</em></p>
<p>Lemma 2 holds even if costs are restricted to be of the form <span class="math-container">$4^{d(i,j)}$</span> for some metric <span class="math-container">$d$</span>.
(But, for the instance in the proof,
OP's parameter <span class="math-container">$k$</span> must be <span class="math-container">$\Omega( \log n)$</span>.
For instances where <span class="math-container">$k = o(\log n)$</span>,
the standard algorithm for finding the minimum,
ignoring costs, has competitive ratio at most <span class="math-container">$4^k$</span> = <span class="math-container">$o(n)$</span>.)</p>
<hr />
<p><em>Proof for Lemma 1.</em>
As the algorithm proceeds,
define the <em>current partial order</em>
to be the partial order <span class="math-container">$\prec$</span> induced on the elements of <span class="math-container">$S$</span>
by the comparisons made so far.
(That is, <span class="math-container">$x \prec y$</span> if
the outcomes of the comparisons made so far
imply that <span class="math-container">$x$</span> is smaller than <span class="math-container">$y$</span>.)
We say <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are (currently) <em>independent</em>
if neither <span class="math-container">$x \prec y$</span> nor <span class="math-container">$y\prec x$</span>.
A <em>root</em> is an element that has not yet lost a comparison.</p>
<p>Let <span class="math-container">$C(x,y)$</span> denote the cost of comparing <span class="math-container">$x$</span> to <span class="math-container">$y$</span>.
Here's the algorithm:</p>
<ol>
<li>while the partial order has at least two roots:</li>
<li><span class="math-container">$~~~$</span> among the independent pairs containing at least one root, let <span class="math-container">$(x, y)$</span> minimize <span class="math-container">$C(x,y)$</span></li>
<li><span class="math-container">$~~~$</span> compare <span class="math-container">$(x, y)$</span></li>
<li>let <span class="math-container">$r$</span> be the root element; return <span class="math-container">$r$</span></li>
</ol>
<p>Each comparison reduces the number of independent
pairs by at least 1, and reduces the number of roots by at most 1,
so the loop will terminate, and when it does there will be a single root.
That root, <span class="math-container">$r$</span>, must be the minimum element,
because every other element has lost a comparison.
So the algorithm is correct.
Next we bound the competitive ratio.</p>
<p>First we bound the cost of those comparisons
such that <span class="math-container">$(x, y)$</span> contains a root other than <span class="math-container">$r$</span>.
Let <span class="math-container">$X$</span> be any node other than <span class="math-container">$r$</span>.
Let <span class="math-container">$(X, y_1), (X, y_2), \ldots, (X, y_k)$</span>
be the sequence of comparisons made to <span class="math-container">$X$</span>
while <span class="math-container">$X$</span> is a root.
<span class="math-container">$X$</span> loses the last such comparison <span class="math-container">$(X, y_k)$</span>,
and wins every preceding comparison <span class="math-container">$(X, y_i)$</span> (with <span class="math-container">$i&lt;k$</span>).
The sequence has non-decreasing cost
and at most <span class="math-container">$n-1$</span> elements,
so its total cost is at most <span class="math-container">$(n-1) C(X, y_k)$</span>.</p>
<p>Let OPT denote an optimal set of comparisons.
OPT is sufficient to prove that <span class="math-container">$r$</span> is the minimum,
so OPT contains some comparison <span class="math-container">$(X, p(X))$</span> that <span class="math-container">$X$</span> loses.
When the algorithm compared <span class="math-container">$X$</span> to <span class="math-container">$y_k$</span>,
the element <span class="math-container">$X$</span> was still a root,
so <span class="math-container">$X$</span> and <span class="math-container">$p(X)$</span> were still independent.
So the pair <span class="math-container">$(X, p(X))$</span> was one of the pairs considered for comparison
in Line 2.
So the greedy choice of <span class="math-container">$y_k$</span> implies that <span class="math-container">$C(X, y_k) \le C(X, p(Z))$</span>.</p>
<p>We consider every element <span class="math-container">$X \ne r$</span> (as above),
and charge the cost of the algorithm's comparisons
<span class="math-container">$(X, y_1), \ldots, (X, y_k)$</span> to the comparison <span class="math-container">$(X, p(X))$</span> in OPT
that <span class="math-container">$X$</span> loses.
(Any given comparison <span class="math-container">$(X, p(X))$</span> is charged at most once
in this way, because <span class="math-container">$X$</span> is the loser of <span class="math-container">$(X, p(X))$</span>.)
Thus, the total cost the algorithm pays for such comparisons
is at most <span class="math-container">$n-1$</span> times the cost of OPT.</p>
<p>It remains to bound the cost of the algorithm's comparisons of the form <span class="math-container">$(r, y)$</span>, where <span class="math-container">$r$</span> is the minimum and <span class="math-container">$y$</span> is any element that is not a root at the time of the comparison.</p>
<p>When such a comparison <span class="math-container">$(r, y)$</span> is made, there is at least one more root, say <span class="math-container">$X$</span>, other than <span class="math-container">$r$</span>.  As <span class="math-container">$X$</span> is still a root,
the pair <span class="math-container">$(X, p(X))$</span> is independent,
So <span class="math-container">$C(r, y) \le C(X, p(X))$</span>.
We charge the cost of the comparison <span class="math-container">$(r, y)$</span> to OPT's comparison <span class="math-container">$(X, p(X))$</span>.
Since <span class="math-container">$r$</span> is involved in at most <span class="math-container">$n-1$</span> comparisons,
the comparisons in OPT are charged at most <span class="math-container">$n-1$</span> times in this way.
Hence, the algorithm pays at most <span class="math-container">$n-1$</span> times the cost of OPT
for these comparisons.</p>
<p>Hence, the algorithm is <span class="math-container">$2(n-1)$</span>-competitive. <span class="math-container">$~~~\Box$</span></p>
<hr />
<p><em>Proof sketch for Lemma 2.</em>  Fix an arbitrarily large integer <span class="math-container">$m$</span>.
Let <span class="math-container">$S=\{x, z\}\cup\{y_1, y_2, \ldots, y_m\}$</span>, so <span class="math-container">$n=|S|=m+2$</span>.
Make the cost of comparing <span class="math-container">$x$</span> to any <span class="math-container">$y_i$</span> be 0.
Make the cost of comparing <span class="math-container">$z$</span> to any <span class="math-container">$y_i$</span> be 1.
Make every other comparison cost <span class="math-container">$n$</span>.
(Here we assume arbitrary costs are allowed.
Later we address the restricted case.)</p>
<p>Choose the ordering as follows.
Choose a random index <span class="math-container">$r$</span> uniformly from <span class="math-container">$[m]$</span>.
Make <span class="math-container">$x$</span> smaller than each <span class="math-container">$y_i$</span>.
Make <span class="math-container">$z$</span> smaller than each <span class="math-container">$y_i$</span> except <span class="math-container">$y_r$</span>.
Make <span class="math-container">$z$</span> larger than <span class="math-container">$y_r$</span>.
Order the remaining pairs arbitrarily,
consistent with the partial order specified above.
This defines the problem instance.</p>
<p>Note that <span class="math-container">$x$</span> is the minimum.
Indeed, <span class="math-container">$x$</span> is less than every <span class="math-container">$y_i$</span>,
and <span class="math-container">$y_r$</span> is less than <span class="math-container">$z$</span>.
Furthermore, there is a set of comparisons of cost 1 that shows this:
compare <span class="math-container">$x$</span> to every <span class="math-container">$y_i$</span> (at cost 0)
then compare <span class="math-container">$y_r$</span> to <span class="math-container">$z$</span> (at cost 1).</p>
<p>On the other hand, consider any (correct) online algorithm.
If the algorithm ever makes a comparison of cost <span class="math-container">$n$</span>,
its competitive ratio is at least <span class="math-container">$n$</span>, so assume otherwise.
To know that <span class="math-container">$z$</span> is not the minimum,
it must compare <span class="math-container">$y_r$</span> to <span class="math-container">$z$</span>.
But, not knowing <span class="math-container">$r$</span>, by the symmetry of the <span class="math-container">$y_i$</span>'s,
it must compare (in expectation) at least <span class="math-container">$m/2$</span> <span class="math-container">$y_i$</span>'s to <span class="math-container">$z$</span>
before it finds <span class="math-container">$y_r$</span>.
Each of these <span class="math-container">$m/2 = \Omega(n)$</span> comparisons costs 1.</p>
<p>It follows that the competitive ratio of the algorithm is <span class="math-container">$\Omega(n)$</span>.</p>
<hr />
<p>Finally consider the case that costs must be of the form <span class="math-container">$4^{d(x,y)}$</span> for some metric <span class="math-container">$d$</span> on pairs in <span class="math-container">$S$</span>.
This constraint is equivalent to the constraint
that the comparison costs satisfy
<span class="math-container">$1 \le C(x, z) \le C(x, y) \times C(y, z)$</span>
for all element triples <span class="math-container">$(x, y, z)$</span>.</p>
<p>Modify the instance above by adjusting
the comparison costs as follows.
Make the cost of comparing <span class="math-container">$x$</span> to any <span class="math-container">$y_i$</span> be <span class="math-container">$m^2$</span>.
Make the cost of comparing any <span class="math-container">$y_i$</span> to <span class="math-container">$z$</span> be <span class="math-container">$m^3$</span>.
Make the cost any other comparison <span class="math-container">$m^4$</span>.
This defines the comparison costs.
Note that <span class="math-container">$C(i, k) \le C(i, j) C(j, k)$</span> for all triples,
as required.</p>
<p>Choose the ordering of <span class="math-container">$S$</span> just as before.
That is, choose a random index <span class="math-container">$r$</span> uniformly from <span class="math-container">$[m]$</span>.
Make <span class="math-container">$x$</span> smaller than each <span class="math-container">$y_i$</span>.
Make <span class="math-container">$z$</span> smaller than each <span class="math-container">$y_i$</span> except <span class="math-container">$y_r$</span>.
Make <span class="math-container">$z$</span> larger than <span class="math-container">$y_r$</span>.
Order the remaining pairs arbitrarily,
consistent with the partial order specified above.
This defines the problem instance.</p>
<p>As before, <span class="math-container">$x$</span> is the minimum.
(Indeed, <span class="math-container">$x$</span> is less than every <span class="math-container">$w_i$</span>,
every <span class="math-container">$w_i$</span> is less than every <span class="math-container">$y_j$</span>,
and <span class="math-container">$y_r$</span> is less than <span class="math-container">$z$</span>.)
Furthermore, there is a set of comparisons of cost <span class="math-container">$2 m^3$</span> that shows this:
compare <span class="math-container">$x$</span> to every <span class="math-container">$y_i$</span> (total cost <span class="math-container">$m\times m^2$</span>),
then compare <span class="math-container">$y_r$</span> to <span class="math-container">$z$</span> (at cost m^3).</p>
<p>On the other hand, consider any (correct) online algorithm.
If the algorithm ever makes a comparison of cost <span class="math-container">$m^4$</span>,
its competitive ratio is at least <span class="math-container">$m = \Omega(n)$</span>,
so assume otherwise.
To know that <span class="math-container">$z$</span> is not the minimum,
it must compare <span class="math-container">$y_r$</span> to <span class="math-container">$z$</span>.
But, not knowing <span class="math-container">$r$</span>, by the symmetry of the <span class="math-container">$y_i$</span>'s,
it must compare (in expectation) at least <span class="math-container">$m/2$</span> <span class="math-container">$y_i$</span>'s to <span class="math-container">$z$</span>
before it finds <span class="math-container">$y_r$</span>.
Each of these <span class="math-container">$m/2$</span> comparisons costs <span class="math-container">$m^3$</span>.</p>
<p>It follows that algorithm pays at least <span class="math-container">$\Omega(m^4)$</span>,
and the competitive ratio of the algorithm is <span class="math-container">$\Omega(m) = \Omega(n)$</span>.  <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2024-03-03T14:20:53.637Z
2024-03-03T19:32:38.220Z
2024-03-03T19:32:38.220Z
Neal Young
<p>A start is:</p>

<ol>
<li>Sort all elements of your cost matrix C</li>
<li>Perform the lowest cost comparison first, putting the loser in set NOPE</li>
<li>For each subsequent cost comparison, if either of the the two elements is in NOPE, don't perform the comparison</li>
<li>You have to keep going until all but one element is in NOPE, which is n-1 comparisons.</li>
</ol>

<p>Is this a decent algorithm?  Depends on the relative cost of sorting C vs. doing the comparisons in S:</p>

<ul>
<li>For any item you are evaluating, if there were a comparison cheaper than the current one being performed, it has already been performed, and the current item won that comparison</li>
<li>Cost == n^2 numeric comparisons to sort C, plus n-1 comparisons of S</li>
</ul>

<p>-t.</p>

CC BY-SA 3.0
2012-08-10T17:24:37.927Z
Yes, this is one obvious greedy algorithm.  No, the cost is the sum of the costs of the individual comparisons performed by the algorithm, as given by the matrix $C_{i,j}$.
Jeffε
CC BY-SA 3.0
2012-08-10T17:48:38.077Z
Thanks! I already thought about this obvious greedy approach (which is what I'm gonna use if nothing better comes up). The problem is if it gives any guarantees on the competitive ratio.
George
CC BY-SA 3.0
2012-08-11T00:59:59.187Z
@JeffE - yes, the cost is the n-1 comparisons with their associated costs, but also the cost of sorting the cost matrix
Tristan Reid
CC BY-SA 3.0
2012-08-11T01:07:55.373Z
@George B. - If the cost of sorting C is relatively cheap, I don't think there's a better algorithm for doing this.  This algorithm will always perform exactly n-1 comparisons, never 1 more or 1 less.  The comparisons that it performs will always be the n-1 cheapest ones.  I think greed is good...
Tristan Reid
CC BY-SA 3.0
2012-08-11T01:15:07.247Z
No, it won't always be the cheapest ones. For example, let A > B > C and $d_(A,B)$ = 1, $d_(A,C)$ = 2 and $d_(B,C)$ = 1. If you first compare $A$ and $B$ and then compare $A$ to $C$ the total cost will be 4^1 + 4^2 = 20, whereas if you first compare $B$ to $C$ and then $A$ to $B$ the cost will be 4^1 + 4^1 = 8, so such a greedy algorithm won't work here. And yes, sorting C is not a problem.
George
CC BY-SA 3.0
2012-08-11T02:10:47.293Z
Thanks George. I may be misunderstanding, but if A>B>C, A would be a member of NOPE after the first comparison AB, and so AC wouldn't be done. I get your point tho.
I understand it's not optimal, but I don't think there's a better algo for every possible cost matrix.

I'll try to think of ways to decompose the cost matrix - worst case is you remove a cheap element, which could be used to cheaply remove others. Another greedy algo would be determine the list of cheapest compares for each i. Problem is worst case becomes a sum - expected cost depends on distribution of costs.
Tristan Reid
CC BY-SA 3.0
2012-08-11T05:39:59.547Z
@TristanReid: "Cost" does not mean the running time of the algorithm.  In particular, Sorting C takes _time_, but it incurs zero _cost_, because it does not require comparing elements of S.  Think of _cost_ as being measured in dollars, while _time_ is measured in seconds. The primary goal here is to minimize the total _cost_ of the comparisons; minimizing _time_ is a secondary concern.
Jeffε
CC BY-SA 3.0
2012-08-11T15:08:30.650Z
Thanks JeffE, I understood that, didn't know if there were any costs external to C.
Tristan Reid
CC BY-SA 3.0
2012-08-11T20:13:05.173Z
For a particular i in S, my algorithm will always find the best case if i is the first comparison, and can only be the worst case if i is the last comparison (if all other comparisons have been made).
Tristan Reid
CC BY-SA 3.0
2012-08-11T20:35:20.637Z
Sorry, accidentally wiped out rest of comment: Worst case can only occur for at most 1 comparison, which will always be the last one.  If you imagine a better algorithm that avoided this case, its best case is better, worst case is worst, and E(cost) is dependent on the distribution of C. I still don't see a better algorithm that will be good for all possible C matrices. I think in order to refine the question you need to determine which you're trying to optimize: best case, worst case or expected? Greedy optimizes worst case.
Tristan Reid
CC BY-SA 3.0
2012-08-14T13:08:46.280Z
Greedy _sometimes_ optimizes the worst case; any claim that a particular greedy algorithm optimizes a particular objective  requires a proof.  "I still don't see a better algorithm" is not a proof.  Also: Expected case is only well-defined if an input distribution has been specified, and it hasn't, so it isn't. Nobody cares about the best case.
Jeffε
CC BY-SA 3.0
2012-08-16T14:52:10.530Z
JeffE, what I mean about 'better algorithm' is that I'm curious to see if there are any improvements that will be globally useful for a C, it's obviously not intended as a proof.
Tristan Reid
CC BY-SA 3.0
2012-08-16T15:03:29.377Z
I believe 'clever adversary' is a bit misleading - the worst-case is completely deterministic dependent on C before any comparisons are performed.  Also, I don't understand the comment "best possible algorithm can be forced to perform all 3 comparisons", the greedy algorithm would always perform exactly two in the example you gave, and would not be worst case for that C. I don't think greedy will ever be worst-case for any C. For a worst case, imagine the last [(x-1)th] comparison involving elements i and j is the most expensive comparison in C. For this to be true under greedy, (see next)
Tristan Reid
CC BY-SA 3.0
2012-08-16T15:31:02.160Z
this implies (w/ caveat to follow) that all other comparison have involved either i or j and that both i and j have won all comparisons that they were involved in. The caveat is if there is more than one most expensive comparison, but if this is true you can always do worse than greedy by performing both most expensive comparisons. In the case where most expensive is unique, the (x-2)th step must have involved i,j along w/ 1 other element k. Assume ik was performed: k must have not won, and C(ik)<=C(jk). We therefore always either have a worse case by doing ij+jk or we have equal worst cases.
Tristan Reid
CC BY-SA 3.0
2012-08-10T17:17:21.597Z
2012-08-10T17:17:21.597Z
Tristan Reid
<p>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 <strong>cost</strong> $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.</p>

<p>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. </p>

<p><strong>Is there an online algorithm that finds a sequence of comparisons of small total cost that finds the smallest element of $S$?</strong>  There is no online algorithm that finds the set of comparisons with <em>minimum</em> total cost, even when $n=3$, but perhaps there is an online algorithm with small competitive ratio.  </p>

<p>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?</p>

<p>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 <em>optimal</em> online algorithm is still impossible in this setting.</p>

<p>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.) </p>

CC BY-SA 3.0
2012-08-08T20:44:10.003Z
Wait, now I'm confused.  If you know both the values and the pairwise comparison costs in advance, minimizing the total comparison cost is equivalent to computing a **minimum-cost arborescence** in a complete acyclic directed graph.  But if you _don't_ know the values, but only discover their order by actually performing comparisons, there is _no_ online strategy that always finds the smallest element using comparisons of minimum total cost; a clever adversary can force you to waste money.  **Which version are you interested in?**
Jeffε
CC BY-SA 3.0
2012-08-08T20:49:38.407Z
Ok, maybe I did not make my question clear enough. The values are unknown and are "revealed" by comparisons (not really, say comparisons return only if an object is greater, equal or smaller than another). So I'm interested in the second version. Btw never heard of the minimum-cost arborescence. At least I learned something new.
George
CC BY-SA 3.0
2012-08-08T21:22:56.770Z
You should edit your question to make this point explicit.  To answer your short questions: I don't know whether the problem is already known, but performing the optimum set of comparisons online is not NP-complete, because it's **impossible** (unless $n=2$).  The best you can hope for is a small competitive ratio.
Jeffε
CC BY-SA 3.0
2012-08-09T18:35:39.557Z
Edited for clarity (I hope) and to emphasize that this is an _online_ algorithms question.  Please check that I haven't screwed up the problem statement too much!
Jeffε
CC BY-SA 3.0
2012-08-09T21:40:57.607Z
This is alot better! Thank you very much. I also added that the distance between any two objects is bounded above by some integer k.
George
CC BY-SA 3.0
2012-08-10T17:50:39.027Z
@Jeffe thanks for putting a bounty on my question! I'm also interested in ANY hint/idea/reference/solution, even for special cases.
George
CC BY-SA 4.0
2024-03-03T21:18:18.723Z
[@Jeffe, just in case you are interested, I added an answer for general $n$.]
Neal Young
<cc.complexity-theory><ds.algorithms><reference-request><online-algorithms>
Cheap online selection with weighted comparisons
George
# Cheap online selection with weighted comparisons

(Asked by: username_0 on 2012-08-08)

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.)

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, online-algorithms
> **Comments:**
> **username_1**: Wait, now I'm confused.  If you know both the values and the pairwise comparison costs in advance, minimizing the total comparison cost is equivalent to computing a **minimum-cost arborescence** in a complete acyclic directed graph.  But if you _don't_ know the values, but only discover their order by actually performing comparisons, there is _no_ online strategy that always finds the smallest element using comparisons of minimum total cost; a clever adversary can force you to waste money.  **Which version are you interested in?**  
> **username_0**: Ok, maybe I did not make my question clear enough. The values are unknown and are "revealed" by comparisons (not really, say comparisons return only if an object is greater, equal or smaller than another). So I'm interested in the second version. Btw never heard of the minimum-cost arborescence. At least I learned something new.  
> **username_1**: You should edit your question to make this point explicit.  To answer your short questions: I don't know whether the problem is already known, but performing the optimum set of comparisons online is not NP-complete, because it's **impossible** (unless $n=2$).  The best you can hope for is a small competitive ratio.  
> **username_1**: Edited for clarity (I hope) and to emphasize that this is an _online_ algorithms question.  Please check that I haven't screwed up the problem statement too much!  
> **username_0**: This is alot better! Thank you very much. I also added that the distance between any two objects is bounded above by some integer k.  
> **username_0**: @Jeffe thanks for putting a bounty on my question! I'm also interested in ANY hint/idea/reference/solution, even for special cases.  
> **username_2**: [@Jeffe, just in case you are interested, I added an answer for general $n$.]  

---

## 3 answers

### Answer by username_1 on 2012-08-11. Score: 7

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 > S\_2$.
* If the algorithm compares $S\_1$ to $S\_3$:

  + The adversary declares $S\_1 > S\_3$.
  + The algorithm must compare $S\_2$ and $S\_3$.
  + The adversary declares $S\_2 < 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 < S\_3 < S\_1$.
  + The total cost of the optimal comparisons ($S\_1>S\_2$ and $S\_2
* If the algorithm compares $S\_2$ to $S\_3$:

  + The adversary declares $S\_3 > 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 < S\_1 < S\_3$.
  + The total cost of the optimal comparisons ($S\_1>S\_2$ and $S\_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} > \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.

> **Comments:**
> **username_0**: That is a very good first step! Thanks for your interest in my problem (it seems that you are even more interested than me :) )  
> **username_3**: Nice observation.  Just to note, this analysis assumes a deterministic algorithm unless I am mistaken.  
> **username_1**: Yes, that's right.  A randomized algorithm might do better (in expectation, against an oblivious adversary).  

---

### Answer by username_2 on 2024-03-03. Score: 1

As a function of $n=|S|$, the optimal competitive is $\Theta(n)$:

**Lemma 1.** *There is a deterministic $O(n)$-competitive online algorithm.*

**Lemma 2.** *No deterministic (or randomized) online algorithm is $o(n)$-competitive.*

Lemma 2 holds even if costs are restricted to be of the form $4^{d(i,j)}$ for some metric $d$.
(But, for the instance in the proof,
OP's parameter $k$ must be $\Omega( \log n)$.
For instances where $k = o(\log n)$,
the standard algorithm for finding the minimum,
ignoring costs, has competitive ratio at most $4^k$ = $o(n)$.)

---

*Proof for Lemma 1.*
As the algorithm proceeds,
define the *current partial order*
to be the partial order $\prec$ induced on the elements of $S$
by the comparisons made so far.
(That is, $x \prec y$ if
the outcomes of the comparisons made so far
imply that $x$ is smaller than $y$.)
We say $x$ and $y$ are (currently) *independent*
if neither $x \prec y$ nor $y\prec x$.
A *root* is an element that has not yet lost a comparison.

Let $C(x,y)$ denote the cost of comparing $x$ to $y$.
Here's the algorithm:

1. while the partial order has at least two roots:
2. $~~~$ among the independent pairs containing at least one root, let $(x, y)$ minimize $C(x,y)$
3. $~~~$ compare $(x, y)$
4. let $r$ be the root element; return $r$

Each comparison reduces the number of independent
pairs by at least 1, and reduces the number of roots by at most 1,
so the loop will terminate, and when it does there will be a single root.
That root, $r$, must be the minimum element,
because every other element has lost a comparison.
So the algorithm is correct.
Next we bound the competitive ratio.

First we bound the cost of those comparisons
such that $(x, y)$ contains a root other than $r$.
Let $X$ be any node other than $r$.
Let $(X, y\_1), (X, y\_2), \ldots, (X, y\_k)$
be the sequence of comparisons made to $X$
while $X$ is a root.
$X$ loses the last such comparison $(X, y\_k)$,
and wins every preceding comparison $(X, y\_i)$ (with $i).
The sequence has non-decreasing cost
and at most $n-1$ elements,
so its total cost is at most $(n-1) C(X, y\_k)$.

Let OPT denote an optimal set of comparisons.
OPT is sufficient to prove that $r$ is the minimum,
so OPT contains some comparison $(X, p(X))$ that $X$ loses.
When the algorithm compared $X$ to $y\_k$,
the element $X$ was still a root,
so $X$ and $p(X)$ were still independent.
So the pair $(X, p(X))$ was one of the pairs considered for comparison
in Line 2.
So the greedy choice of $y\_k$ implies that $C(X, y\_k) \le C(X, p(Z))$.

We consider every element $X \ne r$ (as above),
and charge the cost of the algorithm's comparisons
$(X, y\_1), \ldots, (X, y\_k)$ to the comparison $(X, p(X))$ in OPT
that $X$ loses.
(Any given comparison $(X, p(X))$ is charged at most once
in this way, because $X$ is the loser of $(X, p(X))$.)
Thus, the total cost the algorithm pays for such comparisons
is at most $n-1$ times the cost of OPT.

It remains to bound the cost of the algorithm's comparisons of the form $(r, y)$, where $r$ is the minimum and $y$ is any element that is not a root at the time of the comparison.

When such a comparison $(r, y)$ is made, there is at least one more root, say $X$, other than $r$. As $X$ is still a root,
the pair $(X, p(X))$ is independent,
So $C(r, y) \le C(X, p(X))$.
We charge the cost of the comparison $(r, y)$ to OPT's comparison $(X, p(X))$.
Since $r$ is involved in at most $n-1$ comparisons,
the comparisons in OPT are charged at most $n-1$ times in this way.
Hence, the algorithm pays at most $n-1$ times the cost of OPT
for these comparisons.

Hence, the algorithm is $2(n-1)$-competitive. $~~~\Box$

---

*Proof sketch for Lemma 2.* Fix an arbitrarily large integer $m$.
Let $S=\{x, z\}\cup\{y\_1, y\_2, \ldots, y\_m\}$, so $n=|S|=m+2$.
Make the cost of comparing $x$ to any $y\_i$ be 0.
Make the cost of comparing $z$ to any $y\_i$ be 1.
Make every other comparison cost $n$.
(Here we assume arbitrary costs are allowed.
Later we address the restricted case.)

Choose the ordering as follows.
Choose a random index $r$ uniformly from $[m]$.
Make $x$ smaller than each $y\_i$.
Make $z$ smaller than each $y\_i$ except $y\_r$.
Make $z$ larger than $y\_r$.
Order the remaining pairs arbitrarily,
consistent with the partial order specified above.
This defines the problem instance.

Note that $x$ is the minimum.
Indeed, $x$ is less than every $y\_i$,
and $y\_r$ is less than $z$.
Furthermore, there is a set of comparisons of cost 1 that shows this:
compare $x$ to every $y\_i$ (at cost 0)
then compare $y\_r$ to $z$ (at cost 1).

On the other hand, consider any (correct) online algorithm.
If the algorithm ever makes a comparison of cost $n$,
its competitive ratio is at least $n$, so assume otherwise.
To know that $z$ is not the minimum,
it must compare $y\_r$ to $z$.
But, not knowing $r$, by the symmetry of the $y\_i$'s,
it must compare (in expectation) at least $m/2$ $y\_i$'s to $z$
before it finds $y\_r$.
Each of these $m/2 = \Omega(n)$ comparisons costs 1.

It follows that the competitive ratio of the algorithm is $\Omega(n)$.

---

Finally consider the case that costs must be of the form $4^{d(x,y)}$ for some metric $d$ on pairs in $S$.
This constraint is equivalent to the constraint
that the comparison costs satisfy
$1 \le C(x, z) \le C(x, y) \times C(y, z)$
for all element triples $(x, y, z)$.

Modify the instance above by adjusting
the comparison costs as follows.
Make the cost of comparing $x$ to any $y\_i$ be $m^2$.
Make the cost of comparing any $y\_i$ to $z$ be $m^3$.
Make the cost any other comparison $m^4$.
This defines the comparison costs.
Note that $C(i, k) \le C(i, j) C(j, k)$ for all triples,
as required.

Choose the ordering of $S$ just as before.
That is, choose a random index $r$ uniformly from $[m]$.
Make $x$ smaller than each $y\_i$.
Make $z$ smaller than each $y\_i$ except $y\_r$.
Make $z$ larger than $y\_r$.
Order the remaining pairs arbitrarily,
consistent with the partial order specified above.
This defines the problem instance.

As before, $x$ is the minimum.
(Indeed, $x$ is less than every $w\_i$,
every $w\_i$ is less than every $y\_j$,
and $y\_r$ is less than $z$.)
Furthermore, there is a set of comparisons of cost $2 m^3$ that shows this:
compare $x$ to every $y\_i$ (total cost $m\times m^2$),
then compare $y\_r$ to $z$ (at cost m^3).

On the other hand, consider any (correct) online algorithm.
If the algorithm ever makes a comparison of cost $m^4$,
its competitive ratio is at least $m = \Omega(n)$,
so assume otherwise.
To know that $z$ is not the minimum,
it must compare $y\_r$ to $z$.
But, not knowing $r$, by the symmetry of the $y\_i$'s,
it must compare (in expectation) at least $m/2$ $y\_i$'s to $z$
before it finds $y\_r$.
Each of these $m/2$ comparisons costs $m^3$.

It follows that algorithm pays at least $\Omega(m^4)$,
and the competitive ratio of the algorithm is $\Omega(m) = \Omega(n)$. $~~~~\Box$


---

### Answer by username_4 on 2012-08-10. Score: -3

A start is:

1. Sort all elements of your cost matrix C
2. Perform the lowest cost comparison first, putting the loser in set NOPE
3. For each subsequent cost comparison, if either of the the two elements is in NOPE, don't perform the comparison
4. You have to keep going until all but one element is in NOPE, which is n-1 comparisons.

Is this a decent algorithm? Depends on the relative cost of sorting C vs. doing the comparisons in S:

* For any item you are evaluating, if there were a comparison cheaper than the current one being performed, it has already been performed, and the current item won that comparison
* Cost == n^2 numeric comparisons to sort C, plus n-1 comparisons of S

-t.

> **Comments:**
> **username_1**: Yes, this is one obvious greedy algorithm.  No, the cost is the sum of the costs of the individual comparisons performed by the algorithm, as given by the matrix $C_{i,j}$.  
> **username_0**: Thanks! I already thought about this obvious greedy approach (which is what I'm gonna use if nothing better comes up). The problem is if it gives any guarantees on the competitive ratio.  
> **username_4**: @JeffE - yes, the cost is the n-1 comparisons with their associated costs, but also the cost of sorting the cost matrix  
> **username_4**: @George B. - If the cost of sorting C is relatively cheap, I don't think there's a better algorithm for doing this.  This algorithm will always perform exactly n-1 comparisons, never 1 more or 1 less.  The comparisons that it performs will always be the n-1 cheapest ones.  I think greed is good...  
> **username_0**: No, it won't always be the cheapest ones. For example, let A > B > C and $d_(A,B)$ = 1, $d_(A,C)$ = 2 and $d_(B,C)$ = 1. If you first compare $A$ and $B$ and then compare $A$ to $C$ the total cost will be 4^1 + 4^2 = 20, whereas if you first compare $B$ to $C$ and then $A$ to $B$ the cost will be 4^1 + 4^1 = 8, so such a greedy algorithm won't work here. And yes, sorting C is not a problem.  
> **username_4**: Thanks George. I may be misunderstanding, but if A>B>C, A would be a member of NOPE after the first comparison AB, and so AC wouldn't be done. I get your point tho. I understand it's not optimal, but I don't think there's a better algo for every possible cost matrix.  I'll try to think of ways to decompose the cost matrix - worst case is you remove a cheap element, which could be used to cheaply remove others. Another greedy algo would be determine the list of cheapest compares for each i. Problem is worst case becomes a sum - expected cost depends on distribution of costs.  
> **username_1**: @TristanReid: "Cost" does not mean the running time of the algorithm.  In particular, Sorting C takes _time_, but it incurs zero _cost_, because it does not require comparing elements of S.  Think of _cost_ as being measured in dollars, while _time_ is measured in seconds. The primary goal here is to minimize the total _cost_ of the comparisons; minimizing _time_ is a secondary concern.  
> **username_4**: Thanks JeffE, I understood that, didn't know if there were any costs external to C.  
> **username_4**: For a particular i in S, my algorithm will always find the best case if i is the first comparison, and can only be the worst case if i is the last comparison (if all other comparisons have been made).  
> **username_4**: Sorry, accidentally wiped out rest of comment: Worst case can only occur for at most 1 comparison, which will always be the last one.  If you imagine a better algorithm that avoided this case, its best case is better, worst case is worst, and E(cost) is dependent on the distribution of C. I still don't see a better algorithm that will be good for all possible C matrices. I think in order to refine the question you need to determine which you're trying to optimize: best case, worst case or expected? Greedy optimizes worst case.  
> **username_1**: Greedy _sometimes_ optimizes the worst case; any claim that a particular greedy algorithm optimizes a particular objective  requires a proof.  "I still don't see a better algorithm" is not a proof.  Also: Expected case is only well-defined if an input distribution has been specified, and it hasn't, so it isn't. Nobody cares about the best case.  
> **username_4**: JeffE, what I mean about 'better algorithm' is that I'm curious to see if there are any improvements that will be globally useful for a C, it's obviously not intended as a proof.  
> **username_4**: I believe 'clever adversary' is a bit misleading - the worst-case is completely deterministic dependent on C before any comparisons are performed.  Also, I don't understand the comment "best possible algorithm can be forced to perform all 3 comparisons", the greedy algorithm would always perform exactly two in the example you gave, and would not be worst case for that C. I don't think greedy will ever be worst-case for any C. For a worst case, imagine the last [(x-1)th] comparison involving elements i and j is the most expensive comparison in C. For this to be true under greedy, (see next)  
> **username_4**: this implies (w/ caveat to follow) that all other comparison have involved either i or j and that both i and j have won all comparisons that they were involved in. The caveat is if there is more than one most expensive comparison, but if this is true you can always do worse than greedy by performing both most expensive comparisons. In the case where most expensive is unique, the (x-2)th step must have involved i,j along w/ 1 other element k. Assume ik was performed: k must have not won, and C(ik)<=C(jk). We therefore always either have a worse case by doing ij+jk or we have equal worst cases.  

---

