4
$\begingroup$

I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison.

The intuitive algorithm would be comparing them linearly: compare two items, compare the biggest with the next one, repeat. That would give us a total of $N-1$ comparisons.

Since I couldn't come up with anything, I want to know if there is some algorithm to do this more efficiently (making fewer comparisons), taking advantage of subset comparison being allowed.

$\endgroup$
2
$\begingroup$

Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:

  • If one of the sets is bigger than the other, we say that its sum is larger.
  • If the two sets have equal size, we say that their sums are equal.

We can represent each comparison as a vector of length $n$: the comparison $\sum_{i \in A} w_i \gtrless \sum_{i \in B} w_i?$ (where $w_i$ are the weights) corresponds to the vector $1_A - 1_B$, i.e., the vector having value $1$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value $0$ elsewhere.

Let $\mathbf{x}_1,\ldots,\mathbf{x}_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m < n-1$), and let $\mathbf{1}$ be the constant $1$ vector. Since $m+1 < n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}_1,\ldots,\mathbf{x}_m,\mathbf{1}$. We can assume that $|v_i| \leq 1$ for all $i$.

Consider the vector $\mathbf{w}_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| < 1/n$. It is not hard to check that $\mathbf{w}_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}_\delta$ and $\mathbf{w}_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.

This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum_i x_i w_i)$.

$\endgroup$
  • $\begingroup$ Conclussion: there's no way, is it? (I'm sorry to ask this, but I'm bad with all this vector stuff and could not understand completely what you were talking about) $\endgroup$ – Iaka Noe Feb 26 at 17:22
  • $\begingroup$ That's what I would conclude from the argument. $\endgroup$ – Yuval Filmus Feb 26 at 17:24
  • $\begingroup$ IIUC, you're showing that each comparison can be computed as a dot product of 2 vectors whose result is either positive ("first set is larger"), zero ("equal") or negative ("second set is larger"), and then showing that for any set of fewer than $n-1$ comparisons of equal-size sets, there always exist at least 2 weight vectors for which every dot product is zero (since $\mathbf x_i \cdot \mathbf w_{\pm\delta} = \mathbf x_i \cdot \mathbf 1 \pm \delta \mathbf x_i \cdot \mathbf v$, and both terms are zero, for different reasons) -- but which have different maximal values. ... $\endgroup$ – j_random_hacker Feb 27 at 0:28
  • $\begingroup$ ... There are 2 things I don't yet understand: (1) Can the restriction to equal-size comparisons be done away with? (2) Why is it important to include the condition $|\delta| < 1/n$? $\endgroup$ – j_random_hacker Feb 27 at 0:28
  • $\begingroup$ Your two questions are related. I fix the weights in such a way that if you compare sets of different cardinalities, then the larger one is heavier. $\endgroup$ – Yuval Filmus Feb 27 at 3:26

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.