The centdian subtree on tree networks Original Research Article

This paper describes an O(n log n) algorithm for finding the optimal location of a tree shaped facility of a specified size in a tree network with n nodes, using the centdian criterion: a convex combination of the weighted average distance and the maximum weighted distance from the facility to the demand points (nodes of the tree). These optimization criteria introduced by Halpern, combine the weighted median and weighted center objective functions. Therefore they capture more real-world problems and provide good ways to trade-off minisum (efficiency) and minimax (equity) approaches.