Complexity of the Virtual Network Embedding with uniform demands
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider · 2025
Read Complexity of the Virtual Network Embedding with uniform demands by Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10154.txt.
Description
Amal Benhamiche and co-authors draw the border between easy and hard network embedding in a 2025 paper. Virtual network embedding assigns virtual machines and links onto real hardware, the combinatorial heart of network slicing in modern telecom.
The problem is fiercely hard in general, so the team strips away uneven demand sizes to study structure alone. They test practical shapes for both networks, trees, cycles, wheels, and cliques. When the physical network is a tree or a cycle, greedy and dynamic programming methods solve the problem fast. Close cousins of those cases snap back to NP-hard. The resulting map tells engineers which layouts admit exact planning and which force them into heuristics.
Catalog record
| CREATOR | Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10154