  This paper proposes a new approximation algorithm for the offline Virtual
Network Embedding Problem (VNEP) with latency constraints. Given is a set of
virtual networks with computational demands on nodes and bandwidth demands
together with latency bounds on the edges. The VNEP's task is to feasibly embed
a subset of virtual networks on a shared physical infrastructure, e.g., a data
center, while maximizing the attained profit. In contrast to existing works,
our approximation algorithm AFlex allows for (slight) violations of the latency
constraints in order to greatly lower the runtime. To obtain this result, we
use a reduction to the Restricted Shortest Path Problem (RSP) and leverage a
classic result by Goel et al. We complement our formal analysis with an
extensive simulation study demonstrating the computational benefits of our
approach empirically. Notably, our results generalize to any other additive
edge metric besides latency, including loss probability.

Networking and Internet Architecture