Selection under partial information
The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $\Theta(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This...