共查询到20条相似文献,搜索用时 31 毫秒
1.
Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ
n
and a pattern string P∈Σ
m
, for each i=1,2,…,n−m+1 define L
p
(i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L
p
distance is to compute L
p
(i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L
1 matching (pattern matching with an L
1 distance) we show a reduction of the string matching with mismatches problem to the L
1 matching problem and we present an algorithm that approximates the L
1 matching up to a factor of 1+ε, which has an
O(\frac1e2nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)
run time. Then, the L
2 matching problem (pattern matching with an L
2 distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L
∞ matching up to a factor of 1+ε with a run time of
O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)
. We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog 4
m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric. 相似文献
2.
Maurice Jansen 《Theory of Computing Systems》2011,49(2):343-354
The determinantal complexity of a polynomial f(x
1,x
2,…,x
n
) is the minimum m such that f=det
m
(L(x
1,x
2,…,x
n
)), where L(x
1,x
2,…,x
n
) is a matrix whose entries are affine forms in the x
i
s over some field $\mbox {$\mbox {. 相似文献
3.
Davod Khojasteh Salkuyeh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(5):953-961
In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where
A ? \mathbbRn ×nA\in {\mathbb{R}}^{n \times n} and
B ? \mathbbRm ×mB\in {\mathbb{R}}^{m \times m} are crisp M-matrices, C is an n×mn\times m fuzzy matrix and X is unknown. We first transform this system to an (mn)×(mn)(mn)\times (mn) fuzzy system of linear equations. Then, we investigate the existence and uniqueness of a fuzzy solution to this system. We
use the accelerated over-relaxation method to compute an approximate solution to this system. Some numerical experiments are
given to illustrate the theoretical results. 相似文献
4.
Fast Algorithms for the Density Finding Problem 总被引:1,自引:0,他引:1
We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences.
Given a sequence A=(a
1,w
1),(a
2,w
2),…,(a
n
,w
n
) of n ordered pairs (a
i
,w
i
) of numbers a
i
and width w
i
>0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i
*,j
*) over all O(n
2) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑
r=i
j
w
r
≤u such that its density
is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog 2
m) time and O(n+mlog m) space, where
and w
min=min
r=1
n
w
r
. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem.
Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security
Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001. 相似文献
5.
Amotz Bar-Noy Richard E. Ladner Tami Tamir Tammy VanDeGrift 《Journal of Scheduling》2012,15(2):141-155
The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈(w
1,ℓ
1),(w
2,ℓ
2),…,(w
n
,ℓ
n
)〉 of n pairs of positive integers that are associated with the jobs 1,2,…,n, respectively. The processing length of job i is ℓ
i
slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule
all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of
job i is at most w
i
slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard
even for unit-length jobs and a (1+ε)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=?i=1n(1/wi)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal
number of machines might be arbitrarily larger than the generalized lower bound W(I)=?i=1n(li/wi)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods,
different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ε)W(I)+logw
max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal
for some special cases, and computational experiments show that it performs very well in practice. 相似文献
6.
We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet
and let p,n be integers such that
p £ \fracn2p\leq \frac{n}{2}
. A length-n string over Σ, α=(α
1,…,α
n
), has the property Period(p) if for every i,j∈{1,…,n}, α
i
=α
j
whenever i≡j (mod p). For an integer parameter
g £ \fracn2,g\leq \frac{n}{2},
the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property
Period( £ \fracn2)\mathit{Period}(\leq \frac{n}{2})
is also called Periodicity. 相似文献
7.
Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds,
of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower
bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n
−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ
n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ
n))−n
−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p. 相似文献
8.
A combination method of the Newton iteration and parallel finite element algorithm is applied for solving the steady Navier-Stokes
equations under the strong uniqueness condition. This algorithm is motivated by applying the Newton iterations of m times for a nonlinear problem on a coarse grid in domain Ω and computing a linear problem on a fine grid in some subdomains
Ω
j
⊂Ω with j=1,…,M in a parallel environment. Then, the error estimation of the Newton iterative parallel finite element solution to the solution
of the steady Navier-Stokes equations is analyzed for the large m and small H and h≪H. Finally, some numerical tests are made to demonstrate the the effectiveness of this algorithm. 相似文献
9.
A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d
G
(x,y)≤ℓ≤n−1, where d
G
(x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that
the n-dimensional generalized hypercube Q
n
(k
1,k
2,…,k
n
) is panconnected if and only if k
i
≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube
Q3nQ^{3}_{n}
is panconnected. 相似文献
10.
Parallel integer sorting and simulation amongst CRCW models 总被引:1,自引:0,他引:1
Sanjeev Saxena 《Acta Informatica》1996,33(7):607-619
In this paper a general technique for reducing processors in simulation without any increase in time is described. This results
in an O(√log n) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log log n); the same as that for simulating PRIORITY on ARBITRARY. This is used to obtain an O(log n/log log n+√log n (log log m− log log n)) time algorithm for sorting n integers from the set {0,…, m−1}, m≧n, with a processor-time product of O(n log log m log log n) on a TOLERANT CRCW PRAM. New upper and lower bounds for ordered chaining problem on an allocated COMMON CRCW model are also
obtained. The algorithm for ordered chaining takes O(log n/log log n) time on an allocated PRAM of size n. It is shown that this result is best possible (upto a constant multiplicative factor) by obtaining a lower bound of Ω(r log n/(log r+log log n)) for finding the first (leftmost one) live processor on an allocated-COMMON PRAM of size n of r-slow virtual processors (one processor simulates r processors of allocated PRAM). As a result, for ordered chaining problem, “processor-time product” has to be at least Ω(n log n/log log n) for any poly-logarithmic time algorithm.
Algorithm for ordered-chaining problem results in an O(log N/log log N) time algorithm for (stable) sorting of n integers from the set {0,…, m−1} with n-processors on a COMMON CRCW PRAM; here N=max(n, m). In particular if, m=n
O(1)
, then sorting takes Θ(log n/log log n) time on both TOLERANT and COMMON CRCW PRAMs. Processor-time product for TOLERANT is O(n(log log n)2). Algorithm for COMMON uses n processors.
Received August 13, 1992/June 30, 1995 相似文献
11.
V. I. Levin 《Cybernetics and Systems Analysis》2012,48(2):304-312
The problem of synthesis of a dynamic process in some prescribed form at the output of a logical (n,1)-port device is formulated for a given dependence b = f(a
1,…, a
n
) of switching the output signal on moments a
1,…, a
n
of switching input signals, where f is a continuous-logic function. A regular procedure is proposed to solve the problem
by constructing an (n,1)-port device that implements the required dependence f. Solutions for all possible typical cases and a solution algorithm for the general case are given. 相似文献
12.
It is proved that the system of word equations x
i
1=y
i
1
y
i
2…y
i
n
, i=1, 2,…, ⌈n/2⌉ +1, has only cyclic solutions. Some sharpenings concerning the cases n=5, 7 and n≥9 are derived as well as results concerning the general system of equations x
i
1
x
i
2…x
i
m
=y
i
1
y
i
2…y
i
n
, i=1, 2,… . Applications to test sets of certain bounded languages are considered.
Received: 18 May 1995/2 January 1996 相似文献
13.
Surface approximation to scanned data 总被引:6,自引:0,他引:6
A method to approximate scanned data points with a B-spline surface is presented. The data are assumed to be organized in
the form of Q
i,j, i=0,…,n; j=0,…,m
i, i.e., in a row-wise fashion. The method produces a C
(p-1, q-1) continuous surface (p and q are the required degrees) that does not deviate from the data by more than a user-specified tolerance. The parametrization
of the surface is not affected negatively by the distribution of the points in each row, and it can be influenced by a user-supplied
knot vector. 相似文献
14.
Maxim A. Babenko 《Theory of Computing Systems》2010,46(1):59-79
Let G be an undirected graph and $\mathcal{T}=\{T_{1},\ldots,T_{k}\}Let G be an undirected graph and
T={T1,?,Tk}\mathcal{T}=\{T_{1},\ldots,T_{k}\}
be a collection of disjoint subsets of nodes. Nodes in T
1∪⋅⋅⋅∪T
k
are called terminals, other nodes are called inner. By a
T\mathcal{T}
-path we mean a path P such that P connects terminals from distinct sets in
T\mathcal{T}
and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of
T\mathcal{T}
-paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity
O(mn
2), where n and m denote the numbers of nodes and edges in G, respectively. 相似文献
15.
In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning
these classes is the Permanent and Determinant Problem: Given a field
\mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij ’s, and the equality is in
\mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n2)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2. 相似文献
16.
We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
,
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
, and
O(?{logT}loglogT)O(\sqrt{\log T}\log\log T)
, respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ
22 spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation
metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ
22 spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications
to approximation algorithms, the study of such ℓ
22 spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that,
in a certain sense we make precise, ℓ
22 spreading metrics approximate permutation metrics on n points to a factor of
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
. 相似文献
17.
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time 总被引:1,自引:1,他引:0
Marius Zimand 《Computational Complexity》2008,17(2):220-253
18.
19.
《Computers & Mathematics with Applications》2002,43(8-9):951-964
We construct an important transform to obtain sufficient conditions for the oscillation of all solutions of delay partial difference equations with positive and negative coefficients of the form Am+1,n + Am,n+1 − Amn + pmnAm−k−1 − qmnAm−k′,n−l′ = 0, where m, n = 0, 1, …, and k, k′, l′, l are nonnegative integers, p, q ϵ (0, ∞), the coefficients {qmn} and {pmn} are sequences of nonnegative real numbers. 相似文献
20.
L. B. Morales 《Theory of Computing Systems》1997,30(4):367-382
HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x
1+···+x
n whenx=(x
1, …,x
n) inR
n. A mapf:R
n →R is call adiagonal function of dimensionn iff|N
n is a bijection ontoN and, for allx, y inN
n, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2
n−2 inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd
n of such functions is much greater than 2
n−2 forn>3. These combinatorial ideas also give an inductive procedure to constructd
n+1
diagonal orderings of {1, …,n}. 相似文献