A note on hierarchical hubbing for a generalization of the VPN problem
Abstract
Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. The notion of "hierarchical hubbing" was introduced (in the narrow context of a specific robust network design question), by Olver and Shepherd [2010]. Hierarchical hubbing allows for routings with a multiplicity of "hubs" which are connected to the terminals and to each other in a treelike fashion. Recently, Fréchette et al. [2013] explored this notion much more generally, focusing on its applicability to an extension of the wellstudied hose model that allows for upper bounds on individual pointtopoint demands. In this paper, we consider hierarchical hubbing in the context of a previously studied (and extremely natural) generalization of the hose model, and prove that the optimal hierarchical hubbing solution can be found efficiently. This result is relevant to a recently proposed generalization of the "VPN Conjecture".
 Publication:

arXiv eprints
 Pub Date:
 June 2014
 arXiv:
 arXiv:1406.7841
 Bibcode:
 2014arXiv1406.7841O
 Keywords:

 Computer Science  Data Structures and Algorithms;
 Computer Science  Networking and Internet Architecture;
 F.2.2;
 C.2.1
 EPrint:
 14 pages, 1 figure