  The Virtual Network Embedding Problem (VNEP) captures the essence of many
resource allocation problems of today's infrastructure providers, which offer
their physical computation and networking resources to customers. Customers
request resources in the form of Virtual Networks, i.e. as a directed graph
which specifies computational requirements at the nodes and communication
requirements on the edges. An embedding of a Virtual Network on the shared
physical infrastructure is the joint mapping of (virtual) nodes to physical
servers together with the mapping of (virtual) edges onto paths in the physical
network connecting the respective servers.
  This work initiates the study of approximation algorithms for the VNEP.
Concretely, we study the offline setting with admission control: given multiple
request graphs the task is to embed the most profitable subset while not
exceeding resource capacities. Our approximation is based on the randomized
rounding of Linear Programming (LP) solutions. Interestingly, we uncover that
the standard LP formulation for the VNEP exhibits an inherent structural
deficit when considering general virtual network topologies: its solutions
cannot be decomposed into valid embeddings. In turn, focusing on the class of
cactus request graphs, we devise a novel LP formulation, whose solutions can be
decomposed into convex combinations of valid embedding. Proving performance
guarantees of our rounding scheme, we obtain the first approximation algorithm
for the VNEP in the resource augmentation model.
  We propose two types of rounding heuristics and evaluate their performance in
an extensive computational study. Our results indicate that randomized rounding
can yield good solutions (even without augmentations). Specifically, heuristic
rounding achieves 73.8% of the baseline's profit, while not exceeding
capacities.
