An approximation algorithm for the edge-dilation k-center problem

An approximation algorithm for the edge-dilation k-center problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.