A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

DOI10.1137/1.9781611973730.83zbMath1372.68304OpenAlexW4255366398MaRDI QIDQ5363105

Timothy Naumovitz, Michael E. Saks

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.83

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Space-efficient algorithms for longest increasing subsequence

This page was built for publication: A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity