On ultrametric 1-median selection

被引：1
作者：
Chang, Ching-Lueh [1 ]
机构：
[1] Yuan Ze Univ, Dept Comp Sci & Engn, Taoyuan, Taiwan
来源：
THEORETICAL COMPUTER SCIENCE | 2020年 / 828卷
关键词：
1-median selection; Sublinear time algorithms; Ultrametric spaces; Metric spaces; Closeness centrality;
D O I：
10.1016/j.tcs.2020.04.021
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Consider the problem of finding a point in a finite ultrametric space with the minimum average distance to all points. We give this problem a Monte Carlo O ((log(2)(1/epsilon))/epsilon(3))-time (1 + epsilon)-approximation algorithm with success probability 1 - 0 (epsilon), for all epsilon > 0. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：65 / 69
页数：5
相关论文
共 10 条
1