patternMinor
Finding max value algorithm with subset comparison
Viewed 0 times
withvaluecomparisonalgorithmmaxfindingsubset
Problem
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.
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.
Solution
Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:
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)$.
- 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)$.
Context
StackExchange Computer Science Q#104876, answer score: 2
Revisions (0)
No revisions yet.