Open Research Index

On the Virtual Network Embedding polytope

Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider

arXivarxiv/2601.11419Jan 16, 2026cs.DMscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2601.11419
curl -X POST /api/v1/records/arxiv/2601.11419/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.11419/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'