1,721,043 research outputs found
Approximating the maximum consecutive subsums of a sequence
No full textWe 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
Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
No full textWe 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 (and possibly one occurrence) of
Parikh vectors in a bit string. Recently, several attempts have been tried to build indexes
for all Parikh vectors of a binary string in subquadratic time.
However, to the best of our knowledge, no algorithm is know to date which can beat by more than a polylogarithmic factor
the natural exhaustive procedure.
Our result implies an approximate construction of an index for all Parikh vectors of a binary string in time,
for any constant
Such index is approximate, in the sense that it leaves a small chance for false positives, i.e., Parikh vectors might be
reported which are not actually present in the string. No false negative is 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 sub-quadratic running time
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Fractional decompositions of dense hypergraphs
No full textLet H0 be a fixed hypergraph. A fractional H0-decomposition of a hypergraph H is an assignment of nonnegative real weights to the copies of H0 in H such that for each edge e ∈ E(H), the sum of the weights of copies of H0 containing e is precisely one. Let k and r be positive integers with k> r> 2, and let Kr k denote the complete r-uniform hypergraph with k vertices. We prove that there exists a positive constant α = α(k, r) such that every r-uniform hypergraph with n (sufficiently large) vertices in which every (r − 1)-set is contained in at least n(1 − α) edges has a fractional Kr k-decomposition. Using our result together with a recent result of Rödl, Schacht, Siggers and Tokushige, we obtain the following corollary. For every r-uniform hypergraph H0, there exists a positive constant α = α(H0) such that every r-uniform hypergraph H in which every (r − 1)-set is contained in at least n(1 − α) edges has an H0-packing that covers |E(H)|(1 − on(1)) edges
- …
