On the computational complexity of the virtual network embedding problem

DOI10.1016/j.endm.2016.03.028zbMath1351.90036OpenAlexW2403593353MaRDI QIDQ325446

Edoardo Amaldi, Arie M. C. A. Koster, Stefano Coniglio, Martin Tieves

Publication date: 18 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2016.03.028

zbMATH Keywords

computational complexitycombinatorial optimizationinapproximabilityvirtual network embedding

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (3)

Unnamed Item ⋮ A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines ⋮ Compact and extended formulations for the virtual network embedding problem

Cites Work

• Virtual network provisioning across multiple substrate networks
• A survey of network virtualization
• The complexity of the 0/1 multi-knapsack problem
• Some simplified NP-complete graph problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Finding Large Clique Minors is Hard
• Unnamed Item

This page was built for publication: On the computational complexity of the virtual network embedding problem