TCS-TR-A-12-58Date: Tue Jun 19 17:26:31 2012 Title: Fast Approximation Algorithm for the 1-Median Problem Authors: Koji Tabata, Atsuyoshi Nakamura and Mineichi Kudo Contact:
Abstract. We present a fast approximation algorithm for the 1-median problem. Our algorithm can be applied to metric undirected graphs with node weight. Given a node v, our algorithm repeatedly executes a process of finding a node with higher centrality, in which an approximate centrality of each node v' is calculated for the subgraph called the best kNSPGS of (v,v'). The best kNSPGS of (v,v') is a subgraph that contains the shortest path tree of v, and approximate centralities of all the nodes v' for the subtrees can be calculated more efficiently than their exact centralities for the original graph. We empirically show that our algorithm runs much faster and has better approximation ratio than a sophisticated existing method called DTZ. We demonstrate the effectiveness of our algorithm through experiments. ©Copyright 2012 Authors |