While relatively efficient algorithms are now available for minisum (“median”) and minimax (“center”) network location problems, little attention has been focused on the often realistic cases where both criteria are combined in a single formulation. This paper presents a contribution to the study of such “medi-center” problems. Efficient algorithms are developed for locating a single facility on a tree. The simplicity and efficiency of the algorithms are due to a fundamental convexity property of tree networks.