A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

DOI10.1137/1.9781611973730.83MaRDI QIDQ5363105zbMATH OpenOpenAlexFDO

Authors Timothy Naumovitz, Michael 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

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

Recommendations

• Estimating the sortedness of a data stream
• On the monotonicity of a data stream
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Edit Distance to Monotonicity in Sliding Windows
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited in

(8)

• On the monotonicity of a data stream
• Space-efficient algorithms for longest increasing subsequence
• Estimating the sortedness of a data stream
• Streaming algorithms with one-sided estimation
• Space-efficient algorithms for longest increasing subsequence
• Fluctuated fitting under the \(\ell _1\)-metric
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Streaming and query once space complexity of longest increasing subsequence

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363105)