Basics for sublinear algorithms

Dan Wang, Zhu Han

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

Abstract

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
PublisherSpringer
Pages9-21
Number of pages13
Edition9783319204475
DOIs
Publication statusPublished - 1 Jan 2015

Publication series

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

ASJC Scopus subject areas

  • Computer Science(all)

Cite this