Title :
Research on randomized greedy algorithm for k-median problem
Author_Institution :
Dept. of Inf. Eng., Shandong Jiaotong Univ., Jinan, China
Abstract :
This paper presented a randomized greedy algorithm for k-median problem. First some facilities were drawn at random from the given facility set. Among these sample facilities, there exist k facilities to satisfy that the approximation ratio is at most 3 with high probability, if used to serve the whole given clients. Then, a (3+O ((β-1)In(In(k)/α)))-approximation algorithm was given for this problem. At last, some datasets were used to test the valid of the greedy algorithm.
Keywords :
approximation theory; facility location; greedy algorithms; probability; set theory; approximation ratio; facility set; k-median problem; probability; randomized greedy algorithm; Algorithm design and analysis; Approximation algorithms; Approximation methods; Clustering algorithms; Greedy algorithms; Measurement; Search problems; Algorithm; Greedy; approximation ratio; k-median;
Conference_Titel :
Uncertainty Reasoning and Knowledge Engineering (URKE), 2011 International Conference on
Conference_Location :
Bali
Print_ISBN :
978-1-4244-9985-4
Electronic_ISBN :
978-1-4244-9984-7
DOI :
10.1109/URKE.2011.6007856
