Abstract
We consider computing a longest palindrome in the streaming model, where the symbols arrive onebyone 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= log n / log (1 + epsilon) for approximating the answer with multiplicative error (1 + epsilon). Second, we design three realtime algorithms for this problem. Our Monte Carlo approximation algorithms for both additive and multiplicative versions of the problem use 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.
BibTeX  Entry
@InProceedings{gawrychowski_et_al:LIPIcs:2016:6076,
author = {Pawel Gawrychowski and Oleg Merkurev and Arseny Shur and Przemyslaw Uznanski},
title = {{Tight Tradeoffs for RealTime Approximation of Longest Palindromes in Streams}},
booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages = {18:118:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770125},
ISSN = {18688969},
year = {2016},
volume = {54},
editor = {Roberto Grossi and Moshe Lewenstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6076},
URN = {urn:nbn:de:0030drops60765},
doi = {10.4230/LIPIcs.CPM.2016.18},
annote = {Keywords: streaming algorithms, space lower bounds, realtime algorithms, palin dromes, Monte Carlo algorithms}
}
Keywords: 

streaming algorithms, space lower bounds, realtime algorithms, palin dromes, Monte Carlo algorithms 
Seminar: 

27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) 
Issue Date: 

2016 
Date of publication: 

24.06.2016 