Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs.

Content Distribution and End-to-End Monitoring with Set Cover by Pairs Digital content is housed at data centers located on nodes of a data network. Consumers of this content are also located on network nodes. Content flows from a data center to a consumer on a path defined by a routing protocol, such as open shortest path first. A pair of data centers is said to feasibly serve content to a consumer if there are disjoint paths from each data center to the consumer. In "Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs," Johnson, Breslau, Diakonikolas, Duffield, Gu, Hajiaghayi, Karloff, Resende, and Sen study this problem when the goal is to minimize the number of required data centers to serve a set of consumers. They also study another facility location problem that arises in network traffic monitoring. Both problems are modeled as a set cover-by-pairs problem. The authors provide complexity results, a new lower-bounding integer programming formulation, and several heuristics. The lower bounds are easily computed with a commercial MIP solver and validate the claim of near-optimality of their heuristics. In this paper, we consider two special cases of the "cover-by-pairs" optimization problem that arises when we need to place facilities so that each customer is served by two facilities that reach it by disjoint shortest paths. These problems arise in a network traffic-monitoring scheme proposed by Breslau et al. and have potential applications to content distribution. The "set-disjoint" variant applies to networks that use the open shortest path first routing protocol, and the "path-disjoint" variant applies when multiprotocol label switching routing is enabled, making better solutions possible at the cost of greater operational expense. Although we can prove that no polynomial-time algorithm can guarantee good solutions for either version, we are able to provide heuristics that do very well in practice on instances with real-world network structure. Fast implementations of the heuristics, made possible by exploiting mathematical observations about the relationship between the network instances and the corresponding instances of the cover-by-pairs problem, allow us to perform an extensive experimental evaluation of the heuristics and what the solutions they produce tell us about the effectiveness of the proposed monitoring scheme. For the set-disjoint variant, we validate our claim of near-optimality via a new lower-bounding integer programming formulation. Although computing this lower bound requires solving the NP-hard hitting set problem and can underestimate the optimal value by a linear factor in the worst case, it can be computed quickly by CPLEX, and it equals the optimal solution value for all the instances in our extensive test bed. [ABSTRACT FROM AUTHOR]