We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a ...
详细信息
We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a path connecting vertices L and F) can be decided in logarithmic space and polynomial time, by starting a random walk at L, and checking whether F is hit within some time limit. The randomized algorithm has one-sided error (with small probability, it fails to determine that L and F are connected). The reachability algorithm may be used in order to decide (with one-sided error) whether a graph is connected, by running it n - 1 times, each time with a different target vertex F. This increases the running time by a factor of n. In this paper we give an alternative randomized LOGSPACE algorithm for graph connectivity. Its running time varies between O(n(2)) steps and O(n(3)) steps, depending on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our algorithm has two-sided error.
Resultants characterize the existence of roots of systems of polynomial equations, while their matrix formulae reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has i...
详细信息
Resultants characterize the existence of roots of systems of polynomial equations, while their matrix formulae reduce the computation of all common zeros to a problem in linear algebra. Sparse elimination theory has introduced the sparse resultant, which takes into account the sparse structure of the polynomials, as expressed by the respective supports or Newton polytopes. Sparse resultant, or Newton, matrices generalize Macaulay's matrix and define nontrivial multiples of the sparse resultant from which the latter can be recovered. We exploit their structure with the objective to decrease the complexity of constructing such matrices and of computing the exact resultant. Our present study of these structured matrices implies substantial progress in this direction. Subsequent application of fast matrix- by-vector multiplication shall lead to computational complexity bounds that are roughly quadratic in the matrix size, whereas the existing methods have cubic complexity. Our auxiliary techniques for testing exact and numerical nonsingularity of rectangular matrices may be of some independent interest. Finally, we establish complexity bounds, linear in the number of nonzero terms, for polynomial multiplication, under our model of sparseness.
We prove that (1 - o(l)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low order terms) between the ra...
详细信息
This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which in volves the removal or minimization of degradations caused by noise and...
详细信息
This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which in volves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and as sociated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of only O(ln2log n), where n2 is the number of pixels in the image and l is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur.
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is, computations with structu...
详细信息
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is, computations with structured matrices and solving a system of polynomial equations. In the first part of our paper, we extend the Toeplitz and Hankel structures of matrices and some of their known properties to some new classes of structured (quasi-Hankel and quasi-Toeplitz) matrices, naturally associated to systems of-multivariate polynomial equations. In the second part of the paper, we prove some relations between these structured matrices, which extend the classical relations of the univariate case.
The method of complexity regularization is applied to one hidden-layer radial basis function networks to derive regression estimation bounds and convergence rates for classification. Bounds on the expected risk in ter...
详细信息
We consider the problem of reconstructing the shape of an object from multiple images related by translations, when only small portions of the object can be observed in each image. Lindenbaum and Bruckstein (1988) hav...
详细信息
We consider two-dimensional and axially symmetric critical-state problems in type-II superconductivity, and show that these problems are equivalent to evolutionary quasivariational inequalities. In a special case, whe...
We consider two-dimensional and axially symmetric critical-state problems in type-II superconductivity, and show that these problems are equivalent to evolutionary quasivariational inequalities. In a special case, where the inequalities become variational, the existence and uniqueness of the solution are proved.
Multiway trees, also known as m-ary search trees, are data structures generalising binary search trees. A common probability model for analysing the behaviour of these structures is the random permutation model. The p...
The oriented strip packingproblem is very important to manufacturing industries: given a strip of fixed width and a set of many (> 100) nonconvex polygons with 1, 2, 4, or 8 orientations permitted for each polygon,...
详细信息
暂无评论