An Upper Bound on the Space Complexity of Random Formulae in Resolution
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is .
Análisis comparativo de cálculo de previsiones univariables y función de transferencia, mediante las metodologías de Box-Jenkins y redes neuronales.
Analog solution of a given problem in the back time
Analogie - užitečná heuristická strategie
This article describes a heuristic strategy of analogy and illustrates it by five school mathematics examples. These examples are efficiently solved while using such a strategy.
Analyse syntaxique automatique utilisant une grammaire en chaîne («string grammar»)
Analyses of languages accepted by varietor machines in category
Analysis by synthesis in the light of recent developments in the theory of grammar
Analysis of a class of graph partitioning problems
Analysis of a MX/G(a,b)/1 queueing system with vacation interruption
In this paper, a batch arrival general bulk service queueing system with interrupted vacation (secondary job) is considered. At a service completion epoch, if the server finds at least ‘a’ customers waiting for service say ξ, he serves a batch of min (ξ, b) customers, where b ≥ a. On the other hand, if the queue length is at the most ‘a-1’, the server leaves for a secondary job (vacation) of random length. It is assumed that the secondary job is interrupted abruptly and the server resumes for primary...
Analysis of a MX/G(a,b)/1 queueing system with vacation interruption
In this paper, a batch arrival general bulk service queueing system with interrupted vacation (secondary job) is considered. At a service completion epoch, if the server finds at least ‘a’ customers waiting for service say ξ, he serves a batch of min (ξ, b) customers, where b ≥ a. On the other hand, if the queue length is at the most ‘a-1’, the server leaves for a secondary job (vacation) of random length. It is assumed that the secondary...
Analysis of a near-metric TSP approximation algorithm
The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (Δβ-TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v,u}) + c({u,w})), for some cost function c and any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3β2/2 and is the best known algorithm for the Δβ-TSP, for 1 ≤ β ≤ 2. We provide a complete...
Analysis of Algorithms: An Example of a Sort Algorithm
We analyse three algorithms: exponentiation by squaring, calculation of maximum, and sorting by exchanging in terms of program algebra over an algebra.
Analysis of an approximation algorithm for scheduling indepentent parallel tasks.
Analysis of an N/G/1 finite queue with the supplementary variable method.
Analysis of correlation based dimension reduction methods
Dimension reduction is an important topic in data mining and machine learning. Especially dimension reduction combined with feature fusion is an effective preprocessing step when the data are described by multiple feature sets. Canonical Correlation Analysis (CCA) and Discriminative Canonical Correlation Analysis (DCCA) are feature fusion methods based on correlation. However, they are different in that DCCA is a supervised method utilizing class label information, while CCA is an unsupervised method....
Analysis of finite state automata by state isolation
Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting
This paper studies the gradient flow of a regularized Mumford-Shah functional proposed by Ambrosio and Tortorelli (1990, 1992) for image segmentation, and adopted by Esedoglu and Shen (2002) for image inpainting. It is shown that the gradient flow with initial data possesses a global weak solution, and it has a unique global in time strong solution, which has at most finite number of point singularities in the space-time, when the initial data are in . A family of fully discrete approximation...
Analysis of gradient flow of a regularized Mumford-Shah functional for image segmentation and image inpainting
This paper studies the gradient flow of a regularized Mumford-Shah functional proposed by Ambrosio and Tortorelli (1990, 1992) for image segmentation, and adopted by Esedoglu and Shen (2002) for image inpainting. It is shown that the gradient flow with L2 x L∞ initial data possesses a global weak solution, and it has a unique global in time strong solution, which has at most finite number of point singularities in the space-time, when the initial data are in H1 x H1 ∩ L∞. A family of fully...
Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs
We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also yield polynomial...
Analysis of monotonicity properties of some rule interestingness measures