A fundamental issue in real-world systems, such as sen- sor networks, is the selection of observations which most effectively reduce uncertainty. More specifically, we address the long standing problem of nonmyopically selecting the most informative subset of variables in a graphical model. We present the first efficient random- ized algorithm providing a constant factor (1 − 1/e − ε) approximation guarantee for any ε > 0 with high con- fidence. The algorithm leverages the theory of submod- ular functions, in combination with a polynomial bound on sample complexity. We furthermore prove that no polynomial time algorithm can provide a constant factor approximation better than (1 − 1/e) unless P = NP. Finally, we provide extensive evidence of the effective- ness of our method on two complex real-world datasets.

@inproceedings{krause05near,
	author = {Andreas Krause and Carlos Guestrin},
	booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
	month = {July},
	title = {Near-optimal Nonmyopic Value of Information in Graphical Models},
	year = {2005}}