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

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. In this context, Fréchette et al. (2013) recently explored hierarchical hubbing: a routing strategy involving a multiplicity of "hubs" connected to terminals and each other in a treelike fashion. For a natural generalization of the VPN problem, we prove a structural characterization implying that the optimal hierarchical hubbing solution can be found efficiently, and relate this to a "Generalized VPN Conjecture".

Original languageEnglish
Pages (from-to)191-195
Number of pages5
JournalOperations Research Letters
Volume44
Issue number2
DOIs
Publication statusPublished - 2016

Fingerprint

Robust Design
Network Design
Multiplicity
Routing
Optimization Problem
Generalization
Strategy
Class
Context
Optimization problem
Hub
Network design

Keywords

  • Oblivious routing
  • Robust network design
  • VPN Conjecture

Cite this

@article{05469c068f79449d82edefd84d855050,
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. In this context, Fr{\'e}chette et al. (2013) recently explored hierarchical hubbing: a routing strategy involving a multiplicity of {"}hubs{"} connected to terminals and each other in a treelike fashion. For a natural generalization of the VPN problem, we prove a structural characterization implying that the optimal hierarchical hubbing solution can be found efficiently, and relate this to a {"}Generalized VPN Conjecture{"}.",
keywords = "Oblivious routing, Robust network design, VPN Conjecture",
author = "Neil Olver",
year = "2016",
doi = "10.1016/j.orl.2015.12.020",
language = "English",
volume = "44",
pages = "191--195",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

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

In: Operations Research Letters, Vol. 44, No. 2, 2016, p. 191-195.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Olver, Neil

PY - 2016

Y1 - 2016

N2 - Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. In this context, Fréchette et al. (2013) recently explored hierarchical hubbing: a routing strategy involving a multiplicity of "hubs" connected to terminals and each other in a treelike fashion. For a natural generalization of the VPN problem, we prove a structural characterization implying that the optimal hierarchical hubbing solution can be found efficiently, and relate this to a "Generalized VPN Conjecture".

AB - Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. In this context, Fréchette et al. (2013) recently explored hierarchical hubbing: a routing strategy involving a multiplicity of "hubs" connected to terminals and each other in a treelike fashion. For a natural generalization of the VPN problem, we prove a structural characterization implying that the optimal hierarchical hubbing solution can be found efficiently, and relate this to a "Generalized VPN Conjecture".

KW - Oblivious routing

KW - Robust network design

KW - VPN Conjecture

UR - http://www.scopus.com/inward/record.url?scp=84955464127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955464127&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2015.12.020

DO - 10.1016/j.orl.2015.12.020

M3 - Article

VL - 44

SP - 191

EP - 195

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -