Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables. Find $min(Entropy (x_i | k\,variables))$. Value need not be exact, approximate solutions are fine.
However, I am wondering is it possible to find out the solution to the above mentioned problem. Without resolving to enumerate [brute force approach] all possible subsets of size $k$ from remaining $n-1$ variables. And keep a track of the minimum conditional entropy obtained. $Entropy(x_i | Remaining\,variables)$ is the lowest but I intend to get more tighter bound.