共查询到20条相似文献,搜索用时 15 毫秒
1.
Given q+1 strings (a text t of length n and q patterns m1,…,mq) and a natural number w, the multiple serial episode matching problem consists in finding the number of size w windows of text t which contain patterns m1,…,mq as subsequences, i.e., for each mi, if mi=p1,…,pk, the letters p1,…,pk occur in the window, in the same order as in mi, but not necessarily consecutively (they may be interleaved with other letters). Our main contribution here is an algorithm solving this problem on-line in time O(nq) with an MP-RAM model (which is a RAM model equipped with extra operations). 相似文献
2.
J. Nagy-György 《Information Processing Letters》2008,109(1):23-26
In this paper we investigate the online hypergraph coloring problem. In this online problem the algorithm receives the vertices of the hypergraph in some order v1,…,vn and it must color vi by only looking at the subhypergraph Hi=(Vi,Ei) where Vi={v1,…,vi} and Ei contains the edges of the hypergraph which are subsets of Vi. We show that there exists no online hypergraph coloring algorithm with sublinear competitive ratio. Furthermore we investigate some particular classes of hypergraphs (k-uniform hypergraphs, hypergraphs with bounded matching number, projective planes), we analyse the online algorithm FF and give matching lower bounds for these classes. 相似文献
3.
Adam Strzeboński 《Journal of Symbolic Computation》2011,46(11):1284-1290
We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f1(x),…,fm(x),y1,…,yn), where p∈Q[x,t1,…,tm,y1,…,yn] and f1(x),…,fm(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f1(x),…,fm(x)]. In particular, the algorithm applies when f1(x),…,fm(x) are real exp-log functions or tame elementary functions. 相似文献
4.
We study a bottleneck Steiner tree problem: given a set P={p1,p2,…,pn} of n terminals in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. The problem has applications in the design of wireless communication networks. We give a ratio-1.866 approximation algorithm for the problem. 相似文献
5.
Raphaël Clifford 《Information Processing Letters》2011,111(7):323-325
Consider the following problem. Given u sets of sets A1,…,Au with elements over a universe E={e1,…,en}, the goal is to select exactly one set from each of A1,…,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1−? multiplicative factor, for any ?>0, unless P=NP (Zuckerman, 2006 [12]). 相似文献
6.
Consider a directed rooted tree T=(V,E) of maximal degree d representing a collection V of web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each leaf web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendents, we are interested in minimizing the expected number of steps needed to visit the leaf pages from the home page. We give an O(N2) time algorithm for assigning hotlinks so that the expected number of steps to reach the leaves from the root of the tree is at most H(p)/(log(d+1)−(d/(d+1))logd)+(d+1)/d, where H(p) is the entropy of the probability (frequency) distribution p=〈p1,p2,…,pN〉 on the N leaves of the given tree, i.e., pi is the weight on the ith leaf. The best known lower bound for this problem is H(p)/log(d+1). We also show how to adapt our algorithm to complete trees of a given degree d and in this case we prove it is optimal, asymptotically in d. 相似文献
7.
8.
Jan Krají?ek 《Information Processing Letters》2007,101(4):163-167
We prove that there is a polynomial time substitution (y1,…,yn):=g(x1,…,xk) with k?n such that whenever the substitution instance A(g(x1,…,xk)) of a 3DNF formula A(y1,…,yn) has a short resolution proof it follows that A(y1,…,yn) is a tautology. The qualification “short” depends on the parameters k and n. 相似文献
9.
Arindam Karmakar 《Information Processing Letters》2008,108(6):343-346
Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p1,p2,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log2n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n2). 相似文献
10.
We present a simple and faster solution to the problem of matching a set of patterns with variable length don't cares. Given an alphabet Σ, a pattern p is a word p1@p2?@pm, where pi is a string over Σ called a keyword and @∉Σ is a symbol called a variable length don't care (VLDC) symbol. Pattern p matches a text t if t=u0p1u1…um−1pmum for some u0,…,um∈Σ∗. The problem addressed in this paper is: given a set of patterns P and a text t, determine whether one of the patterns of P matches t.Kucherov and Rusinowitch (1997) [9] presented an algorithm that solves the problem in time O((|t|+|P|)log|P|), where |P| is the total length of keywords in every pattern of P. We give a new algorithm based on Aho-Corasick automaton. It uses the solutions of Dynamic Marked Ancestor Problem of Chan et al. (2007) [5]. The algorithm takes O((|t|+‖P‖)logκ/loglogκ) time, where ‖P‖ is the total number of keywords in every pattern of P, and κ is the number of distinct keywords in P. The algorithm is faster and simpler than the previous approach. 相似文献
11.
Fokko J. van de Bult 《Information Processing Letters》2008,108(5):336-337
We analyze a sorting problem where for every element there is a hard upper bound on the overall number of lost comparisons: Given are n elements and n non-negative integers a1,…,an. The goal is to sort these n elements by pairwise comparisons, subject to the condition that the kth element must not be the loser (= smaller element) in more than ak of its comparisons against the other elements.We completely characterize the sequences a1,…,an for which this sorting problem can be solved. 相似文献
12.
Let F1,…,Fs∈R[X1,…,Xn] be polynomials of degree at most d, and suppose that F1,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F1,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F1(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F1,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F1,…,Fs belong to Z[X1,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F1,…,Fs. 相似文献
13.
How many questions are necessary and sufficient to guess an unknown number x in the set S={1,2,…,n}, by using only comparison questions, that is questions of the type “Is x?a?”, a∈S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d?0 and c=1. 相似文献
14.
For a positive integer c, a c-vertex-ranking of a graph G=(V,E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O(log2n) time using linear number of operations on the EREW PRAM model. 相似文献
15.
Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index 总被引:5,自引:0,他引:5
Andrea Saltelli Ivano Azzini Francesca Campolongo Marco Ratto Stefano Tarantola 《Computer Physics Communications》2010,181(2):259-165
Variance based methods have assessed themselves as versatile and effective among the various available techniques for sensitivity analysis of model output. Practitioners can in principle describe the sensitivity pattern of a model Y=f(X1,X2,…,Xk) with k uncertain input factors via a full decomposition of the variance V of Y into terms depending on the factors and their interactions. More often practitioners are satisfied with computing just k first order effects and k total effects, the latter describing synthetically interactions among input factors. In sensitivity analysis a key concern is the computational cost of the analysis, defined in terms of number of evaluations of f(X1,X2,…,Xk) needed to complete the analysis, as f(X1,X2,…,Xk) is often in the form of a numerical model which may take long processing time. While the computational cost is relatively cheap and weakly dependent on k for estimating first order effects, it remains expensive and strictly k-dependent for total effect indices. In the present note we compare existing and new practices for this index and offer recommendations on which to use. 相似文献
16.
17.
In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p1,p2,p3,…,pn in the plane, we have O(n2) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S. 相似文献
18.
Hyunki Kim Author Vitae Author Vitae 《Pattern recognition》2009,42(9):1777-270
We demonstrate a text-mining method, called associative Naïve Bayes (ANB) classifier, for automated linking of MEDLINE documents to gene ontology (GO). The approach of this paper is a nontrivial extension of document classification methodology from a fixed set of classes C={c1,c2,…,cn} to a knowledge hierarchy like GO. Due to the complexity of GO, we use a knowledge representation structure. With that structure, we develop the text mining classifier, called ANB classifier, which automatically links Medline documents to GO. To check the performance, we compare our datasets under several well-known classifiers: NB classifier, large Bayes classifier, support vector machine and ANB classifier. Our results, described in the following, indicate its practical usefulness. 相似文献
19.
In an undirected graph, paths P1,P2,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s1,t1},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound. 相似文献