Disjoint-Path Facility Location: Theory and Practice

This paper is a theoretical and experimental study of two related facility location problems that emanated from networking. Suppose the authors are given a network modeled as a directed graph G = (V, A), together with (not-necessarily-disjoint) subsets C and F of V, where C is a set of customer loca...

Full description

Saved in:
Bibliographic Details
Main Authors: Breslau, Lee, Diakonikolas, Ilias, Duffield, Nick, Gu, Yu, Hajiaghayi, Mohammad Taghi, Johnson, David S, Karloff, Howard, Resende, Mauricio G C, Sen, Subhabrata
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Heuristic
Network topologies
Routing
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is a theoretical and experimental study of two related facility location problems that emanated from networking. Suppose the authors are given a network modeled as a directed graph G = (V, A), together with (not-necessarily-disjoint) subsets C and F of V, where C is a set of customer locations and F is a set of potential facility locations (and typically C ⊆ F). Their goal is to find a minimum sized subset F' ⊆ F such that for every customer c ... C there are two locations [function of]1, [function of]2 ... F' such that traffic from c to [function of]1 and to [function of]2 is routed on disjoint paths (usually shortest paths) under the network's routing protocols. The authors propose three algorithms that build solutions and determine lower bounds on the optimum solution, and evaluate them on several large real ISP topologies and on synthetic networks designed to reflect real-world LAN/WAN network structure.(ProQuest: ... denotes formulae/symbols omitted.)
ISSN:2164-0300