Article ID: | iaor20051038 |
Country: | Netherlands |
Volume: | 32 |
Issue: | 5 |
Start Page Number: | 491 |
End Page Number: | 495 |
Publication Date: | Sep 2004 |
Journal: | Operations Research Letters |
Authors: | Li Yanjun, Sinha Amitabh, Knemann Jochen, Parekh Ojas |
Keywords: | heuristics |
We provide an approximation algorithm for selecting centers in a complete graph so as to minimize the maximum ratio of the distance between any two nodes via their respective centers to their true graph distance. Placing centers under such an objective function is important in designing efficient communication networks which rely on hubs for routing.