English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Many resource allocation problems in the cloud can be described as a basicVirtual Network Embedding Problem (VNEP): the problem of finding a mapping of arequest graph (describing a workload) onto a substrate graph (describing thephysical infrastructure). Applications range from mapping testbeds (from wherethe problem originated), over the embedding of batch-processing workloads(virtual clusters) to the embedding of service function chains. The differentapplications come with their own specific requirements and constraints,including node mapping constraints, routing policies, and latency constraints.While the VNEP has been studied intensively over the last years, complexityresults are only known for specific models and we lack a comprehensiveunderstanding of its hardness.  This paper charts the complexity landscape of the VNEP by providing asystematic analysis of the hardness of a wide range of VNEP variants, using aunifying and rigorous proof framework. In particular, we show that the problemof finding a feasible embedding is NP-complete in general, and, hence, the VNEPcannot be approximated under any objective, unless P=NP holds. Importantly, wederive NP-completeness results also for finding approximate embeddings, whichmay violate, e.g., capacity constraints by certain factors. Lastly, we provethat our results still pertain when restricting the request graphs to planar ordegree-bounded graphs.

NP-Completeness and Inapproximability of the Virtual Network Embedding Problem and Its Variants