  The growing amount of applications that generate vast amount of data in short
time scales render the problem of partial monitoring, coupled with prediction,
a rather fundamental one. We study the aforementioned canonical problem under
the context of large-scale monitoring of communication networks. We consider
the problem of selecting the "best" subset of links so as to optimally predict
the quantity of interest at the remaining ones. This is a well know NP-hard
problem, and algorithms seeking the exact solution are prohibitively expensive.
We present a number of approximation algorithms that: 1) their computational
complexity gains a significant improvement over existing greedy algorithms; 2)
exploit the geometry of principal component analysis, which also helps us
establish theoretical bounds on the prediction error; 3) are amenable for
randomized implementation and execution in parallel or distributed fashion, a
process that often yields the exact solution. The new algorithms are
demonstrated and evaluated using real-world network data.
