1 Search Results for "Bosman, Thomas"

Document

DOI: 10.4230/LIPIcs.ESA.2017.19

Exploring the Tractability of the Capped Hose Model

Authors: Thomas Bosman and Neil Olver

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

Robust network design concerns the design of networks to support uncertain or varying traffic patterns. An especially important case is the VPN problem, where the total traffic emanating from any node is bounded, but there are no further constraints on the traffic pattern. Recently, Fréchette et al. [INFOCOM, 2013] studied a generalization of the VPN problem where in addition to these so-called hose constraints, there are individual upper bounds on the demands between pairs of nodes. They motivate their model, give some theoretical results, and propose a heuristic algorithm that performs well on real-world instances. Our theoretical understanding of this model is limited; it is APX-hard in general, but tractable when either the hose constraints or the individual demand bounds are redundant. In this work, we uncover further tractable cases of this model; our main result concerns the case where each terminal needs to communicate only with two others. Our algorithms all involve optimally embedding a certain auxiliary graph into the network, and have a connection to a heuristic suggested by Fréchette et al. for the capped hose model in general.

Cite as

Thomas Bosman and Neil Olver. Exploring the Tractability of the Capped Hose Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bosman_et_al:LIPIcs.ESA.2017.19,
  author =	{Bosman, Thomas and Olver, Neil},
  title =	{{Exploring the Tractability of the Capped Hose Model}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.19},
  URN =		{urn:nbn:de:0030-drops-78663},
  doi =		{10.4230/LIPIcs.ESA.2017.19},
  annote =	{Keywords: robust network design, VPN problem}
}

Refine by Author
1 Bosman, Thomas
1 Olver, Neil

Refine by Classification

Refine by Keyword
1 VPN problem
1 robust network design

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Bosman, Thomas"

Exploring the Tractability of the Capped Hose Model

Abstract

Cite as

Thanks for your feedback!

Could not send message