Improved algorithms for minimum cost replicated web contents distribution tree

Recently, Tang and Chanson proposed a minimum cost distribution model for replicated Web contents subject to an expiration-based consistency management. Their model is a progress in that it can consider multiple replicas via the network of servers located on the Web. The proposed greedy heuristic, however, has an undesirable feature that the solution tends to converge to a local optimum at an early stage of the algorithm. In this paper, we propose an algorithm based on a simple idea of preventing the early local convergence. The new algorithm provides solutions whose cost are, on the average, 27% lower than in the previous algorithm.