Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs   In this paper we consider two special cases of the "cover-by-pairs"
optimization problem that arise 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 OSPF routing protocol,
and the "path-disjoint" variant applies when MPLS 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
testbed.

16
The categories of this paper are: stat
30
The categories of this paper are: q-alg
0
The categories of this paper are: hep-ph
4
The categories of this paper are: cond-mat
11
The categories of this paper are: hep-lat
17
The categories of this paper are: q-fin
35
The categories of this paper are: mtrl-th
19
The categories of this paper are: eess
12
The categories of this paper are: nucl-th
25
The categories of this paper are: patt-sol
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
8
The categories of this paper are: hep-ex
2
The categories of this paper are: math
24
The categories of this paper are: dg-ga
3
The categories of this paper are: physics