Before revision:  We study these models under various assumptions on the patience (number of given probes)of the online vertices, and whether edges or offline vertices are weighted in determining the stochastic reward. Our main contribution is to establish new and improved competitive bounds in these four models.In all settings, there is one ideal benchmark (the optimal offline probing algorithm)relative to which the competitive ratio is defined.For establishing competitive ratios we introduce a new LP relaxation which upper bounds the performance of the ideal benchmark .
After revision:  We study these models under various assumptions on the patience (number of given probes)of the online vertices, and whether edges or offline vertices are weighted and online arrivals are adversarial. (2) A 1-1/e ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A 1-1/e ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) 1/e ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order .