We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ(n2) procedure. We show how to construct a (1+ϵ)-approximate index for all Parikh vectors of a binary string in O(nlog^2n/log(1+ϵ), for any constant ϵ>0. Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time.

Approximating the maximum consecutive subsums of a sequence

CICALESE, Ferdinando;
2014

Abstract

We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ(n2) procedure. We show how to construct a (1+ϵ)-approximate index for all Parikh vectors of a binary string in O(nlog^2n/log(1+ϵ), for any constant ϵ>0. Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4413055
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact