Separating sublinear time computations by approximate diameter

Bin Fu, Zhiyu Zhao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationCombinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
Pages79-88
Number of pages10
DOIs
StatePublished - Sep 22 2008
Event2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 - St. John's, NL, Canada
Duration: Aug 21 2008Aug 24 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5165 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Country/TerritoryCanada
CitySt. John's, NL
Period8/21/088/24/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Separating sublinear time computations by approximate diameter'. Together they form a unique fingerprint.

Cite this