Trade-offs on the location of the core node in a network

We consider the problem of selecting a core node in a network under two potentially competing criteria, one being the sum of the distances to a set of terminals, the other being the cost of connecting this core node and the terminals with a Steiner tree. We characterize the worst-case trade-off between approximation ratios for the two objectives. Our results, for example, show the existence of a core node in which both objectives are simultaneously within 1.37 times their optimum value (if we were to disregard the other objective). We also consider the problem of minimizing a weighted sum of the two criteria and perform a worst-case analysis of a simple and fast heuristic, which does not need to enumerate possible core locations. This study was motivated by multimedia applications such as videoconferences or multiplayer games in which user-dependent information has to be sent from the users to a core node to be chosen (at a cost proportional to the sum of the distances from the core node), and then global information has to be multicast back from the core node to all users (at a cost proportional to the Steiner tree cost). (C) 2004 Wiley Periodicals, Inc