Optimal placement of identical resources in a tree

AbstractThe problem of placing a number t of identical resources at nodes of a tree so as to minimize the total expected cost of servicing a set of t requests arriving randomly at nodes is considered. The cost of servicing a particular set of requests is the total distance in the tree between each request and its assigned resource. Distance is measured by the number of edges along the unique path from the request to the resource. Optimal placements can be found in time O(mt), where m is the number of edges in the tree. Allowing resources to be split into fractional-sized pieces which can be placed separately neither reduces the cost of an optimal placement nor provides an obvious way to find optimal placements significantly faster. Simple, natural “fair” placements whose cost differs from optimality by at most the number of edges in the tree are described. For any fixed tree T, the cost of these placements grows as O(t), where the constant implicit in the “O” notation depends on the size and shape of T. In the case of balanced trees with k leaves, that constant is at most 2kφ. The placement problem becomes somewhat simpler for a complete (rooted) d-ary tree with a symmetric probability density function for request arrivals, and in that case slightly stronger results are possible. For example, an optimal placement can be found in time O(min{ℓ, logdt} + t), where ℓ is the height of the tree, and the placement is symmetric and fair