Before revision:  We present an online algorithm that is (1/6)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs . This is the first result to achieve a constant competitive ratio when both arrivals and departures are random and unannounced .
After revision:  We present an online algorithm that is (1/6)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs .