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

DOI10.1016/J.ORL.2015.12.020zbMATH Open1408.90052arXiv1406.7841OpenAlexW1512674954MaRDI QIDQ1785741FDOQ1785741

Authors: Neil Olver 

Publication date: 1 October 2018

Published in: Operations Research Letters (Search for Journal in Brave)

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".

Full work available at URL: https://arxiv.org/abs/1406.7841

Recommendations

• Approximability of robust network design
• Exploring the tractability of the capped hose model
• Approximability of robust network design
• The VPN conjecture is true
• On improving optimal oblivious routing

zbMATH Keywords

robust network designoblivious routingVPN conjecture

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Network design and communication in computer systems (68M10)

Cites Work

• Robust optimization
• Designing Least-Cost Nonblocking Broadband Networks
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Approximability of robust network design
• Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups
• The VPN conjecture is true

Cited In (2)

• Exploring the tractability of the capped hose model
• The VPN Problem with Concave Costs

This page was built for publication: A note on hierarchical hubbing for a generalization of the VPN problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785741)