8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jeffε Aug 8 '12 at 20:44
  • $\begingroup$ 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. $\endgroup$ – George Aug 8 '12 at 20:49
  • 3
    $\begingroup$ 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. $\endgroup$ – Jeffε Aug 8 '12 at 21:22
  • 1
    $\begingroup$ 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! $\endgroup$ – Jeffε Aug 9 '12 at 18:35
  • $\begingroup$ 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. $\endgroup$ – George Aug 9 '12 at 21:40
6
$\begingroup$

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<S_3$) is $\phi$.
  • 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<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} > \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.

$\endgroup$
  • 1
    $\begingroup$ That is a very good first step! Thanks for your interest in my problem (it seems that you are even more interested than me :) ) $\endgroup$ – George Aug 11 '12 at 11:30
  • $\begingroup$ Nice observation. Just to note, this analysis assumes a deterministic algorithm unless I am mistaken. $\endgroup$ – Tsuyoshi Ito Aug 11 '12 at 18:10
  • $\begingroup$ Yes, that's right. A randomized algorithm might do better (in expectation, against an oblivious adversary). $\endgroup$ – Jeffε Aug 11 '12 at 19:20
-3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Jeffε Aug 10 '12 at 17:24
  • $\begingroup$ 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. $\endgroup$ – George Aug 10 '12 at 17:48
  • $\begingroup$ @JeffE - yes, the cost is the n-1 comparisons with their associated costs, but also the cost of sorting the cost matrix $\endgroup$ – Tristan Reid Aug 11 '12 at 0:59
  • $\begingroup$ @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... $\endgroup$ – Tristan Reid Aug 11 '12 at 1:07
  • $\begingroup$ 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. $\endgroup$ – George Aug 11 '12 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.