Given $n_{f}$ sites, each equipped with one facility, and $n_{c}$ cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '$00$: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177--183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244--257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. Algorithms, 4 (2008), pp. 1--27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as another generalization of UFL by allowing each site to hold multiple facilities and show that we can obtain better solutions for this problem. We first give two algorithms with 1.81 and 1.61 approximation ratios in time complexity $O(mR\log m)$ and $O(Rn^{3})$, respectively, where $R$ is the maximum number of facilities required by any city, $m=n_{f}n_{c}$, and $n=\max\{n_{f},n_{c}\}$. Instead of applying the dual-fitting technique that reduces the dual problem's solution to fit the original problem as used in the literature [K. Jain et al., Journal of the ACM, 50 (2003), pp. 795--824; K. Jain, M. Mahdian, and A. Saberi, STOC'02: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, New York, 2002, pp. 731--740; A. Saberi et al., Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Springer, New York, 2001, pp. 127--137], we propose a method called inverse dual-fitting that alters the original problem to fit the dual solution and show that this method is more effective for obtaining solutions of multifactor approximation. We show that applying inverse dual-fitting and factor-revealing techniques our second algorithm is also (1.11,1.78)- and (1,2)-approximation simultaneously. These results can be further used to achieve solutions of 1.52-approximation to FTFA and 4-approximation to the fault tolerant k-facility allocation problem in which the total number of facilities is bounded by $k$. These are currently the best bifactor and single-factor approximation ratios for the problems concerned.

We propose an approximation algorithm for the problem of Fault-Tolerant Facility Location which is implemented in a distributed and asynchronous manner within O(n) rounds of communication. Here n is the number of vertices in the network. As far as we know, the performance guarantee of similar algorithms (centralized) remains unknown except a special case where all cities have a uniform connectivity requirement. In this paper, we assume the shortest-path routing scheme deployed, as well as a constant (given) size of R, which represents the distinct levels of fault-tolerant capability provided by the system (i. e distinct connectivity requirements), and prove that the cost of our solution is no more than |R| · F* + 2 · C* in the general case, where F* and C* are respectively the facility cost and connection cost in an optimal solution. Further more, extensive numerical experiments showed that the quality of our solutions is comparable to the optimal solutions when |R| is no more than 10.

With the emergence of various advanced networks that comprise a group of geographically distributed servers, such as content delivery networks (CDNs) and peer-to-peer (P2P) systems, coordinated en-route Web caching in multiserver networks becomes increasingly attractive but remains of great challenge as solutions for single-server networks become invalid here. In this paper, we first establish mathematical formulation for this problem that takes into account all requests (to any server) that pass through the intermediate nodes on a response path and caches the requested object optimally among these nodes so that system's total gain is maximized. Then, we derive efficient dynamic programming-based methods for finding optimal solutions to the problem for the unconstrained case and two QoS-constrained cases, respectively. For each case, we present a caching scheme to illustrate application of the corresponding method. Finally, we evaluate the proposed schemes on different performance metrics through extensive simulation experiments. The experiment results show that our proposed schemes can yield a steady performance improvement and achieve desired QoS in a multiserver network. To the best of our knowledge, these are the first results for solving the problem of coordinated en-route Web caching in multiserver networks.

Coordinated en-route Web caching has been studied extensively in the recent years. In that scheme, all requests are destined to one server and the requested object is selectively cached at nodes on the route of each response message. In this paper, we extend the scheme to a p-server network and optimize the caching decision by considering all requests that pass through individual nodes on a route, including those destined to servers not on the route. We present an efficient method to find the optimal solution to this problem using dynamic programming technique. Our method can be used for coordinated en-route caching in a p-server network of arbitrary topology.

Dual-server coordinated en-route caching is important because of its basic features as multi-server en-route caching. In this paper, multi-server coordinated en-route caching is formulated as an optimization problem of minimizing total access cost, including transmission cost for all access demands and caching cost of all caches. We first discuss an algorithm for single-server en-route caching in tree networks and then show that this is a special case of another algorithm for dual-server en-route caching in tree networks whose time complexity is O(nh)