On the Virtual Network Embedding polytope

2026/01/16 by Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart +2 · 1 voice · 1 citation
Computer Science · Mathematics · #cs.DM #math.OC

paper · pdf · doi:10.48550/arxiv.2601.11419

Abstract

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.

Citations

• Complexity of the Virtual Network Embedding with uniform demands

Discussions

• Amal Benhamiche, Pierre Fouilhoux, Lucas L\'etocart, Nancy Perrot, Alexis Schneider: On the Virtual Network Embedding polytope https://arxiv.org/abs/2601.11419 https://arxiv.org/pdf/2601.11419 https:/ [bsky, 0 points, 0 comments]

Related

• Complexity of the Virtual Network Embedding with uniform demands
• A decomposition approach for large virtual network embedding
• Virtual Network Embedding via Decomposable LP Formulations: Orientations of Small Extraction Width and Beyond
• On Virtual Network Embedding: Paths and Cycles
• Optimal Virtual Network Embeddings for Tree Topologies