Constructing a strong heuristic function is a central problem in heuristic search.  A common approach is to combine a number of heuristics by maximizing over the values from each.  If a limit is placed on this number, then a subset selection problem arises.  We treat this as an optimization problem, and proceed by translating a natural loss function into a submodular and monotonic utility function under which greedy selection is guaranteed to be near-optimal.  We then extend this approach with a sampling scheme that retains provable optimality.  Our empirical results show large improvements over existing methods, and give new insight into building heuristics for directed domains.