A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

Timothy Naumovitz, Michael Saks

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

9 Scopus citations

Abstract

The distance to monotonicity of a sequence of n numbers is the minimum number of entries whose deletion leaves an increasing sequence. We give the first deterministic streaming algorithm that approximates the distance to monotonicity within a 1-+-ε factor for any fixed ε > 0 and runs in space polylogarithmic in the length of the sequence and the range of the numbers. The best previous deterministic algorithm achieving the same approximation factor required space ω (√n) [9]. Previous polylogarithmic space algorithms were either randomized [10], or had approximation factor no better than 2 [8]. We also present space lower bounds for this problem: Any deterministic streaming algorithm that gets a 1 + ε approximation requires space ω (1/εlog2 (n)) and any randomized algorithm requires space ω (1/ε log2 (n)/ log log (n)).

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages1252-1262
Number of pages11
EditionJanuary
ISBN (Electronic)9781611973747
DOIs
StatePublished - 2015
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/TerritoryUnited States
CitySan Diego
Period1/4/151/6/15

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity'. Together they form a unique fingerprint.

Cite this