9
$\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$
7
  • 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 21:40

3 Answers 3

7
$\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$
3
  • 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, 2012 at 11:30
  • $\begingroup$ Nice observation. Just to note, this analysis assumes a deterministic algorithm unless I am mistaken. $\endgroup$ Aug 11, 2012 at 18:10
  • $\begingroup$ Yes, that's right. A randomized algorithm might do better (in expectation, against an oblivious adversary). $\endgroup$
    – Jeffε
    Aug 11, 2012 at 19:20
1
$\begingroup$

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

$\endgroup$
-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$
14
  • 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, 2012 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, 2012 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$ Aug 11, 2012 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$ Aug 11, 2012 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, 2012 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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