A note on hierarchical hubbing for a generalization of the VPN problem

Research output: ProfessionalWorking paper

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\'echette 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".
Original languageEnglish
Place of PublicationOnline
PublisherarXiv
Number of pages14
StatePublished - 2014

Publication series

NamearXiv
No.1406.7841

Cite this

Olver, N.K. / A note on hierarchical hubbing for a generalization of the VPN problem.

Online : arXiv, 2014. (arXiv; No. 1406.7841).

Research output: ProfessionalWorking paper

@misc{8228860e1a654f9dbf05ebc3deaa6c39,
title = "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\'echette 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{"}.",
author = "N.K. Olver",
note = "arXiv:1406.7841",
year = "2014",
series = "arXiv",
publisher = "arXiv",
number = "1406.7841",
type = "WorkingPaper",
institution = "arXiv",

}

A note on hierarchical hubbing for a generalization of the VPN problem. / Olver, N.K.

Online : arXiv, 2014. (arXiv; No. 1406.7841).

Research output: ProfessionalWorking paper

TY - UNPB

T1 - A note on hierarchical hubbing for a generalization of the VPN problem

AU - Olver,N.K.

N1 - arXiv:1406.7841

PY - 2014

Y1 - 2014

N2 - 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\'echette 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".

AB - 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\'echette 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".

M3 - Working paper

T3 - arXiv

BT - A note on hierarchical hubbing for a generalization of the VPN problem

PB - arXiv

ER -