2014/06/30 by Neil Olver, Olver, Neil
Computer Science · #C.2.1 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1406.7841
14 pages, 1 figure
arxiv created 2014/06/30 · arxiv updated 2014/07/01
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 well-studied hose model that allows for upper bounds on individual point-to-point 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".