zbMATH — the first resource for mathematics

Tight tradeoffs for real-time approximation of longest palindromes in streams. (English) Zbl 1380.68475
Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 18, 13 p. (2016).
Summary: We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exactly using sublinear space is not possible in such a setting, one can still hope for a good approximation guarantee. Our contribution is twofold. First, we provide lower bounds on the space requirements for randomized approximation algorithms processing inputs of length \(n\). We rule out Las Vegas algorithms, as they cannot achieve sublinear space complexity. For Monte Carlo algorithms, we prove a lower bounds of \(\Omega(M\log\min\{|\Sigma|,M\})\) bits of memory; here \(M=n/E\) for approximating the answer with additive error \(E\), and \(M=\frac{\log n}{\log(1+\varepsilon)}\) for approximating the answer with multiplicative error \((1+\varepsilon)\). Second, we design three real-time algorithms for this problem. Our Monte Carlo approximation algorithms for both additive and multiplicative versions of the problem use \({\mathcal O}(M)\) words of memory. Thus the obtained lower bounds are asymptotically tight up to a logarithmic factor. The third algorithm is deterministic and finds a longest palindrome exactly if it is short. This algorithm can be run in parallel with a Monte Carlo algorithm to obtain better results in practice. Overall, both the time and space complexity of finding a longest palindrome in a stream are essentially settled.
For the entire collection see [Zbl 1351.68018].

68W32 Algorithms on strings
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68W25 Approximation algorithms
Full Text: DOI