To reduce monitoring cost, the number of monitors that are to be deployed has to be minimized and the overhead of monitoring flows on the underlying network has to be reduced. In a recent work, we demonstrated, using ILP formulations, that there is a trade-off between these two minimization objectives. However, we have shown that the trade-off could be efficiently balanced by optimizing monitor location and anomaly detection costs jointly. The problem is NP-complete, hence ILPs could not deliver solutions for large networks. In this paper, we address the scalability issues. We propose two greedy algorithms that optimize monitor location cost and anomaly detection cost jointly. The first algorithm is based on an exhaustive heuristic that explores all paths that are candidate to be monitored, in order to select a subset of paths that reduces the total monitoring cost. On the opposite, the second algorithm is based on a selective heuristic that avoids exploring all the candidate paths to further improve scalability. The main challenge of this heuristic is to not degrade the solution quality. The two algorithms have been evaluated through extensive simulations on networks of hundred of billions of paths. The comparison of the solutions delivered by the two algorithms to each other and to the solutions delivered by the ILP demonstrates that the selective algorithm provides near-optimal solutions, while achieving a desirable scalability with respect to the network size and significant reduction of the computation time.