Giampaolo Oriolo

Title:
A short proof of the VPN conjecture on a ring

Abstract:
The Virtual Private Network Design problem is the following optimization problem: We are given a communication network with thresholds on the nodes, representing bounds on the amount of demand that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every pair of nodes such that all traffic matrices respecting these bounds can be routed along the corresponding paths.
An interesting open question is whether every instance of the Virtual Private Network Design problem admits an optimal solution whose support forms a tree: this problem is known in literature as the VPN conjecture. In the talk we show a short and combinatorial proof of the conjecture for rings. The first proof showing the conjecture to hold on rings was given by Hurkens, Keijsper and Stougie (IPCO 06) via linear programming techniques.