Virtual Service Embedding with Time-Varying Load and Provable Guarantees