Is there some generalization of the "Maximum Coverage Problem" for information in random variables?

Question

Say I have a set $X=x_1,x_2,\ldots,x_n$ of random variables, and would like to find a size $k\leq|X|$ subset that contains as much information as possible. This is complicated because the variables may contain redundant information.

It seems, intuitively, that "information" behaves like the size or volume of a set. In particular, I would like to know if some result similar to http://en.wikipedia.org/wiki/Maximum_coverage_problem holds for selecting size $k$ subsets of $X$ that approximately maximize information. If all I can measure is the information content of an ensemble of variables, how good an approximation can I get by, starting from the empty set, always picking the variable that would maximize the information content of my subset ?

I have been told that I need to understand measure theory even to phrase this question correctly, and I apologize if my wording of the question is not rigorous.

Answer 1

The prototypical way of measuring the "information content" of a set of random variables is by evaluating the Shannon entropy of their joint distribution. It is known that entropy is a submodular set function and that it is monotone: the joint distribution of a subset of the random variables cannot have more entropy than that of the set itself. Your question therefore becomes a special case of the following broader question: given the ability to evaluate a monotone, non-negative, submodular set function, how can I compute the $k$-element subset that maximizes this function? There is a greedy algorithm that generalizes the greedy algorithm for the maximum coverage problem: starting from the empty set, repeatedly enlarge your set by adding a single element that yields the greatest increase in the function value, until the number of elements chosen equals $k$. This algorithm, like the greedy algorithm for maximum coverage, achieves an approximation ratio of $e/(e-1)$. (Nemhauser, Wolsey, and Fisher, An analysis of approximations for maximizing submodular set functions, Math. Programming 14 (1978), 265-294.)

There are at least two senses in which this approximation ratio is the best possible under polynomial resource constraints. First, if the algorithm is only allowed to access the function by querying its value at specified sets, then any algorithm achieving an approximation ratio strictly less than $e/(e-1)$ must use an exponential (in $k$) number of queries. (Nemhauser and Wolsey, Best algorithms for approximating the maximum of a submodular set function, Math. Oper. Res. 3:3 (1978), 177-188.) Second, assuming the $P \neq NP$ conjecture, no polynomial-time algorithm can achieve a better approximation ratio, even for the special case of maximum coverage problems.