Cheap online selection with weighted comparisons

Question

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

Answer 1

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.

Answer 2

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$

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