Premium
Trade‐offs on the location of the core node in a network
Author(s) -
Macq JeanFrançois,
Goemans Michel X.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
ISBN - 0-89871-558-X
DOI - 10.1002/net.20028
Subject(s) - node (physics) , core (optical fiber) , steiner tree problem , multicast , computer science , heuristic , set (abstract data type) , tree (set theory) , computer network , value (mathematics) , mathematical optimization , mathematics , combinatorics , telecommunications , artificial intelligence , engineering , structural engineering , programming language , machine learning
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). © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 179–186 2004