Vi anser att datorn är den längsta palindromen i den strömmande modellen, där symbolerna anländer en efter en och vi inte har slumpmässig tillgång till inmatningen. Medan det inte är möjligt att beräkna svaret exakt med hjälp av sublinjärt utrymme i en sådan miljö, kan man fortfarande hoppas på en bra approximation garanti. Vårt bidrag är dubbelt. Först ger vi lägre gränser på utrymmeskraven för randomiserade approximationsalgoritmer bearbetning ingångar av längd n. Vi utesluter Las Vegas algoritmer, eftersom de inte kan uppnå sublinjär rymd komplexitet. För Monte Carlo-algoritmer visar vi en lägre gräns för  och här M = n/E för approximering av svaret med additivt fel E, och M = log n log (1+ε) för approximering av svaret med multiplikativt fel (1 + ε). För det andra utformar vi tre realtidsalgoritmer för detta problem. Våra Monte Carlo approximationsalgoritmer för både additiva och multiplikativa versioner av problemet använder O(M ) minnesord. Således de erhållna lägre gränserna är asymptotiskt tätt upp till en logaritmisk faktor. Den tredje algoritmen är deterministisk och finner en längsta palindrom exakt om den är kort. Denna algoritm kan köras parallellt med en Monte Carlo algoritm för att få bättre resultat i praktiken. På det hela taget är både tids- och rymdkomplexet för att hitta en längsta palindrom i en bäck i huvudsak löst.
Gawrychowski m.fl. REF nyligen generalisera de ovan nämnda lägre gränserna för additivt fel, och även producera ett utrymme lägre gräns för  en log n log(1+ på) för algoritmer med multiplicativt fel (1 +  på).
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}