Basics for sublinear algorithms

Dan Wang, Zhu Han

Research output: Chapter in book / Conference proceedingChapter in an edited book (as author)Academic researchpeer-review

1 Citation (Scopus)


In this chapter, we study the theoretical foundations of sublinear algorithms. We discuss the foundations of approximation and randomization and show the history of the development of sublinear algorithms in the theoretical research line. Intrinsically, sublinear algorithms can be considered as one branch of approximation algorithms with confidence guarantees. A sublinear algorithm says that the accuracy of the algorithm output will not deviate from an error bound and there is high confidence that the error bound will be satisfied. More rigidly, a sublinear algorithm is commonly written as (1 +ε, δ)-approximation in a mathematical form. Here ε is commonly called an accuracy parameter and δ is commonly called a confidence parameter. This accuracy parameter is the same to the approximate factor in approximation algorithms. This confidence parameter is the key trade-off where the complexity of the algorithm can reduce to sublinear. We will rigidly define these parameters in this chapter.

Original languageEnglish
Title of host publicationSpringerBriefs in Computer Science
Number of pages13
Publication statusPublished - 1 Jan 2015

Publication series

NameSpringerBriefs in Computer Science
ISSN (Print)2191-5768
ISSN (Electronic)2191-5776

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Basics for sublinear algorithms'. Together they form a unique fingerprint.

Cite this