On the Virtual Network Embedding polytope
By: Amal Benhamiche , Pierre Fouilhoux , Lucas Létocart and more
Potential Business Impact:
Makes computer networks faster and more efficient.
We initiate the polyhedral study of the Virtual Network Embedding (VNE) problem, which arises in modern telecommunication networks. We propose new valid inequalities for the so-called flow formulation. We then prove, through a dedicated flow decomposition algorithm, that these inequalities characterize the VNE polytope in the case of an embedding of a virtual edge on a substrate path. Preliminary experiments show that the new inequalities propose promising speedups for MIP solvers.
Similar Papers
A decomposition approach for large virtual network embedding
Discrete Mathematics
Makes 5G networks work better and faster.
Complexity of the Virtual Network Embedding with uniform demands
Discrete Mathematics
Makes phone networks faster and more efficient.
Distributed Resource Allocation and Application Deployment in Mesh Edge Networks
Networking and Internet Architecture
Helps mobile devices share internet when moving.