A 16-competitive algorithm for hierarchical median problem  

作　　者：DAI WenQiang 

机构地区：[1]School of Management and Economics,University of Electronic Science and Technology of China

出　　处：《Science China(Information Sciences)》2014年第3期142-148,共7页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No.70901012);Specialized Research Foundation for the Doctoral Program of Higher Education of China (Grant No.200806141084);Fundamental Research Funds for the Central Universities (Grant No.ZYGX2013J134)

摘　　要：The hierarchical median problem consists of finding a hierarchical assignment function sequence of solutions to the well-known k-median problems with growing cardinality. This sequence is said to be r competitive if the cost of each solution is at most r times of the optimum cost of median problem with a same cardinality, where r is called the competitive ratio. Previously the best algorithm available for this problem has competitive ratio 20.71. In this paper an improved aigorithm is proposed with competitive ratio factor 16.The hierarchical median problem consists of finding a hierarchical assignment function sequence of solutions to the well-known k-median problems with growing cardinality. This sequence is said to be r competitive if the cost of each solution is at most r times of the optimum cost of median problem with a same cardinality, where r is called the competitive ratio. Previously the best algorithm available for this problem has competitive ratio 20.71. In this paper an improved aigorithm is proposed with competitive ratio factor 16.

关 键 词：HIERARCHICAL LOCATION MEDIAN ALGORITHM competitive ratio 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]