  We consider the minimum cost intervention design problem: Given the essential
graph of a causal graph and a cost to intervene on a variable, identify the set
of interventions with minimum total cost that can learn any causal graph with
the given essential graph. We first show that this problem is NP-hard. We then
prove that we can achieve a constant factor approximation to this problem with
a greedy algorithm. We then constrain the sparsity of each intervention. We
develop an algorithm that returns an intervention design that is nearly optimal
in terms of size for sparse graphs with sparse interventions and we discuss how
to use it when there are costs on the vertices.

Machine Learning;Discrete Mathematics;Machine Learning