共查询到20条相似文献,搜索用时 31 毫秒
1.
L. Gatteschi 《Calcolo》1979,16(4):447-458
In this paper we obtain a new asymptotic formula for the ultraspherical polynomialP
n
(λ)
(x), asn→∞, with an error term which isO (n
λ−5
) uniformly in the interval −1+δ≤x≤1−δ,δ>0.
Very accurate approximations for the zeros ofP
n
(λ)
(x) are also derived from the preceding formula.
Lavoro eseguito nell'ambito del Gruppo Nazionale per l'Informatica Matematica del C. N. R.. 相似文献
Lavoro eseguito nell'ambito del Gruppo Nazionale per l'Informatica Matematica del C. N. R.. 相似文献
2.
In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and
parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r
j
,p
j
=p,C
j
≤d
j
|− can be solved in O(n
2) time and that the problem of minimizing the maximum lateness can be solved in O(n
2log n) time. For the parallel machine problem P|p-batch,b<n,r
j
,p
j
=p,C
j
≤d
j
|− an O(n
3log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n
3log 2
n) time. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
Given n points, called terminals, in the plane ℝ2 and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ2 and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ2, usually, the Euclidean or the L
1 metric. This problem is known to be NP-hard. In this paper, we study this problem in the L
p
metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog 2
n time for the L
1 and the L
∞ metrics, and the first exact algorithm for the L
p
metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n
k
+nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L
2 metric. 相似文献
6.
The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying
the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood
is empty.
For β≥1, this neighborhood of a pair of points p
i
,p
j
is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p
i
+(β/2)p
j
and (β/2)p
i
+(1−β/2)p
j
, respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p
i
and p
j
.
In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l
1 and l
∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n
5/2logn) [7].
Received April 26, 2000 相似文献
7.
If G is an n vertex maximal planar graph and δ≤1 3, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B contains more than (1−δ)n vertices, no edge from G connects a vertex in A to a vertex in B, and C is a cycle in G containing no more than (√2δ+√2−2δ)√n+O(1) vertices. Specifically, when δ=1 3, the separator C is of size (√2/3+√4/3)√n+O(1), which is roughly 1.97√n. The constant 1.97 is an improvement over the best known so far result of Miller 2√2≈2.82. If non-negative weights adding
to at most 1 are associated with the vertices of G, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B has weight exceeding 1−δ, no edge from G connects a vertex in A to a vertex in B, and C is a simple cycle with no more than 2√n+O(1) vertices.
Received: 8 September 1993/11 December 1995 相似文献
8.
V. M. Kravtsov 《Cybernetics and Systems Analysis》2005,41(6):940-944
To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms α0, α1, ..., α
p−1 with complexities equal to O(np+1), O(np), ..., O(n2) operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of
the objective function.
__________
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 176–181, November–December 2005. 相似文献
9.
Jae-Hun Jung 《Journal of scientific computing》2009,39(1):49-66
The solution of differential equations with singular source terms contains the local jump discontinuity in general and its
spectral approximation is oscillatory due to the Gibbs phenomenon. To minimize the Gibbs oscillations near the local jump
discontinuity and improve convergence, the regularization of the approximation is needed. In this note, a simple derivative
of the discrete Heaviside function H
c
(x) on the collocation points is used for the approximation of singular source terms δ(x−c) or δ
(n)(x−c) without any regularization. The direct projection of H
c
(x) yields highly oscillatory approximations of δ(x−c) and δ
(n)(x−c). In this note, however, it is shown that the direct projection approach can yield a non-oscillatory approximation of the
solution and the error can also decay uniformly for certain types of differential equations. For some differential equations,
spectral accuracy is also recovered. This method is limited to certain types of equations but can be applied when the given
equation has some nice properties. Numerical examples for elliptic and hyperbolic equations are provided.
The current address: Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA. 相似文献
10.
A point (x*,λ*) is called apitchfork bifurcation point of multiplicityp≥1 of the nonlinear systemF(x, λ)=0,F:ℝn×ℝ1→ℝn, if rank∂
xF(x*, λ*)=n−1, and if the Ljapunov-Schmidt reduced equation has the normal formg(ξ, μ)=±ξ
2+
p±μξ=0. It is shown that such points satisfy a minimally extended systemG(y)=0,G:ℝ
n+2→ℝn+2 the dimensionn+2 of which is independent ofp. For solving this system, a two-stage Newton-type method is proposed. Some numerical tests show the influence of the starting
point and of the bordering vectors used in the definition of the extended system on the behavior of the iteration. 相似文献
11.
The longest common subsequence problem (LCS) and the closest substring problem (CSP) are two models for finding common patterns
in strings, and have been studied extensively. Though both LCS and CSP are NP-Hard, they exhibit very different behavior with
respect to polynomial time approximation algorithms. While LCS is hard to approximate within n
δ
for some δ>0, CSP admits a polynomial time approximation scheme. In this paper, we study the longest common rigid subsequence problem
(LCRS). This problem shares similarity with both LCS and CSP and has an important application in motif finding in biological
sequences. We show that it is NP-hard to approximate LCRS within ratio n
δ
, for some constant δ>0, where n is the maximum string length. We also show that it is NP-Hard to approximate LCRS within ratio Ω(m), where m is the number of strings. 相似文献
12.
Embedding of Cycles in Twisted Cubes with Edge-Pancyclic 总被引:1,自引:0,他引:1
In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer
l, 4≤l≤2
n
, a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2
n
, and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n
2+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ
n
for any (u,v)∈E(TQ
n
) and any integer l with 4≤l≤2
n
. 相似文献
13.
We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT
n
, withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T
n
} are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L
2, and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P
n
−1
Tn}, where the sequence{P
n
} is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP
n
−1
T
n
is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp
−1
f. We also prove that the firstm eigenvalues ofP
n
−1
Tn tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned
matricesP
n
−1
Tn are computed. 相似文献
14.
LetC be a binary code of lengthn (i.e., a subset of {0, 1}
n
). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1}
n
is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary
codes is NP-complete.
This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1}
n
,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT
problem is polynomially reducible to the Radius decision problem.
A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v
1
v
2 …v
2n
) | ∀i:v
2i
=v
2i−1}. We show that there is a setY ⊂ {0, 1}2n
such that for everyv ε {0, 1}2n
:v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn. 相似文献
15.
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. 相似文献
16.
A grid (or a mesh) is a two-dimensional permutation: an m× n-grid of size mn is an m× n-matrix where the entries run through the elements {1,2, …, mn}. We prove that if δ1 and δ2 are any two linear orders on {1,2, …, N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size. 相似文献
17.
Lubomir V. Kolev 《Reliable Computing》2006,12(2):121-140
The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝn×n for the general case where the matrix elements aij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λμ, x(μ)), μ = 1, ..., n, is suggested for the case where λμ is a simple eigenvalue. It is based on the use of an affine interval approximation of aij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real
or complex eigenvalue, respectively. 相似文献
18.
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. 相似文献
19.
Abstract. Let P = {p
1
, p
2
, \ldots, p
n
} be a set of n {\lilsf terminal points} in the Euclidean plane, where point p
i
has a {\lilsf service request of grade} g(p
i
) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ⋅s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting
point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p
i
and p
j
there is a path whose minimum grade of service is at least as large as \min(g(p
i
), g(p
j
)) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge
with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the
same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal
points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the
general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies.
A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n
1.5
(log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates
the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm.
Preliminary computational results are presented. 相似文献
20.
The classical RSA is vulnerable to low private exponent attacks (LPEA) and has homomorphism. KMOV based on elliptic curve
E
n
(a,b) over ℤ
n
can resist LPEA but still has homomorphism. QV over E
n
(a,b) not only can resist LPEA but also has no homomorphism. However, QV over E
n
(a,b) requires the existence of points whose order is M
n
= lcm{♯E
p
(a,b), ♯E
q
(a,b)}. This requirement is impractical for all general elliptic curves. Besides, the computation over En(a,b) is quite complicated.
In this paper, we further study conic curve C
n
(a,b) over ℤ
n
and its corresponding properties, and advance several key theorems and corollaries for designing digital signature schemes,
and point out that C
n
(a,b) always has some points whose order is M
n
= lcm{♯E
p
(a,b), ♯E
q
(a,b)}. Thereby we present an improved QV signature over C
n
(a,b), which inherits the property of non-homomorphism and can resist the Wiener attack. Furthermore, under the same security
requirements, the improved QV scheme is easier than that over E
n
(a,b), with respect plaintext embedding, inverse elements computation, points computation and points’ order calculation. Especially,
it is applicable to general conic curves, which is of great significance to the application of QV schemes.
Supported by the National Natural Science Foundation of China (Grant No. 10128103) 相似文献