TY - GEN
T1 - Separating sublinear time computations by approximate diameter
AU - Fu, Bin
AU - Zhao, Zhiyu
PY - 2008/9/22
Y1 - 2008/9/22
N2 - We study sublinear time complexity and algorithm to approximate the diameter for a sequence S∈=∈p 1 p 2∈ ⋯∈p n of points in a metric space, in which every pair of two consecutive points p i and p i∈+∈1 in the sequence S has the same distance. The diameter of S is the largest distance between two points p i and p j in S. The approximate diameter problem is investigated under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations about the sublinear time computations using various versions of the approximate diameter problem based on the restriction about the format of input data.
AB - We study sublinear time complexity and algorithm to approximate the diameter for a sequence S∈=∈p 1 p 2∈ ⋯∈p n of points in a metric space, in which every pair of two consecutive points p i and p i∈+∈1 in the sequence S has the same distance. The diameter of S is the largest distance between two points p i and p j in S. The approximate diameter problem is investigated under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations about the sublinear time computations using various versions of the approximate diameter problem based on the restriction about the format of input data.
UR - http://www.scopus.com/inward/record.url?scp=51849135398&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51849135398&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-85097-7_8
DO - 10.1007/978-3-540-85097-7_8
M3 - Conference contribution
AN - SCOPUS:51849135398
SN - 3540850961
SN - 9783540850960
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 79
EP - 88
BT - Combinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
T2 - 2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Y2 - 21 August 2008 through 24 August 2008
ER -