Exact sizes of networks that select the three or four largest of n elements
Source: hexagonmath.org/abs/2611.00374v1
We study $(t,n)$-selection networks, which move the $t$ largest of $n$ inputs to $t$ given lines in any order, and the least number $\hat U_t(n)$ of comparators in such a network. Alekseev showed that $\hat U_t(n)\ge(n-t)\lceil\lg(t+1)\rceil$. For $t=2^k\ge 4$ we raise this bound by $k-1$ for every $n>t$, and by $2k-5$ when $t\ge 32$; as far as we know, these are the first improvements at powers of two. The proofs follow the weights of the lines, and a pruning step of Yao extends the gain to every $t\ge 3$. For $t=3$, Yao's upper bound $2n-5+\lfloor\lg(n-3)\rfloor$ is exact for $4\le n\le…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00374
curl -X POST /api/v1/records/hexagon/2611.00374/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00374/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'