Disjoint-Path Facility Location: Theory and Practice

Ilias Diakonikolas, Yu Gu, Lee Breslau, Subhabrata Sen, Mohammad Taghi Hajiaghayi, Mauricio G. C. Resende, David S. Johnson, Howard Karloff, Nick Duffield

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper is a theoretical and experimental study of two related facility location problems that emanated from networking. Suppose we 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). Our goal is to find a minimum sized subset F′ ⊆ F such that for every customer c ∊ C there are two locations f1, f2F′ such that traffic from c to f1 and to f2 is routed on disjoint paths (usually shortest paths) under the network's routing protocols.

Although we prove that this problem is impossible to approximate in the worst case even to within a factor of 2log1−εn for any ε > 0 (assuming no NP-complete language can be solved in quasipolynomial time), we show that the situation is much better in practice. We 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. Our main algorithms are (1) an algorithm that performs multiple runs of a straightforward randomized greedy heuristic and returns the best result found, (2) a genetic algorithm that uses the greedy algorithm as a subroutine, and (3) a new “Double Hitting Set” algorithm. All three approaches perform surprising well, although, in practice, the most cost-effective approach is the multi-run greedy algorithm. This yields results that average within 0.7% of optimal for our synthetic instances and within 2.9% for our real-world instances, excluding the largest (and most realistic) one. For the latter instance, the other two algorithms come into their own, finding solutions that are more than three times better than those of the multi-start greedy approach. In terms of our motivating monitoring application, where every customer location can be a facility location, the results are even better. Here the above Double Hitting Set solution is 90% better than the default solution which places a monitor at each customer location - such comparisons help justify the proposed alternative monitoring scheme of [8]. Our results also show that, on average for our real-world instances, we could save an additional 18% by choosing the (shortest path) routes ourselves, rather than taking the simpler approach of relying on the network to choose them for us.

Original languageEnglish
Title of host publication2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX)
Pages60-74
Number of pages15
ISBN (Electronic)978-1-61197-291-7
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Disjoint-Path Facility Location: Theory and Practice'. Together they form a unique fingerprint.

Cite this