We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Boro...
详细信息
We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Borodin which converts uniform boolean circuit depth into sequential (Turing machine) space. The boolean circuits themselves are developed using techniques based on the computation of a primitive element of a suitable zero-dimensional algebra and diophantine considerations. Our algorithms improve considerably the space requirements of the elimination algorithms based on rewriting techniques (Grobner solving), having simultaneously a time performance of the same kind of them.
In a previous article (Cluzeau and Hubert in Appl Algebra Eng Commun Comput 13(5):395-425, 2003), we proved the existence of resolvent representations for regular differential ideals. The present paper provides practi...
详细信息
In a previous article (Cluzeau and Hubert in Appl Algebra Eng Commun Comput 13(5):395-425, 2003), we proved the existence of resolvent representations for regular differential ideals. The present paper provides practical algorithms for computing such representations. We propose two different approaches. The first one uses differential characteristic decompositions whereas the second one proceeds by prolongation and algebraic elimination. Both constructions depend on the choice of a tuple over the differential base field and their success relies on the chosen tuple to be separating. The probabilistic aspect of the algorithms comes from this choice. To control it, we exhibit a family of tuples for which we can bound the probability that one of its element is separating.
It is demonstrated that the rank decision problem for the full class of matrices with polynomial entries can be solved probabilistically, in polynomial time. It is possible to write efficient straight-line programs t...
详细信息
It is demonstrated that the rank decision problem for the full class of matrices with polynomial entries can be solved probabilistically, in polynomial time. It is possible to write efficient straight-line programs to solve the rank decision problem for matrices with real entries. Two well-known techniques, Gaussian elimination and fast matrix multiplication, can be used to write these programs. The Gaussian elimination technique, while easily implemented for integer matrices, does not generalize to real matrices.
The basic probabilistic algorithm for Least Median of Squares regression (LMS) with p parameters is based on repeated drawings of random subsamples of p data points, followed by calculation of the median-squared resid...
详细信息
The basic probabilistic algorithm for Least Median of Squares regression (LMS) with p parameters is based on repeated drawings of random subsamples of p data points, followed by calculation of the median-squared residual with respect to the hyperplane fitted to these p points. The regression plane with the smallest median-squared residual is then treated as an approximate solution. Three improved variants of this algorithm are proposed and compared with regard to their capability to satisfy a necessary condition for LMS and to their empirical performances.
We present probabilistic algorithms for the problems of finding an irreducible polynomial of degree n over a finite field, finding roots of a polynomial, and factoring a polynomial into its irreducible factors over a ...
详细信息
We present probabilistic algorithms for the problems of finding an irreducible polynomial of degree n over a finite field, finding roots of a polynomial, and factoring a polynomial into its irreducible factors over a finite field. All of these problems are of importance in algebraic coding theory, algebraic symbol manipulation, and number theory. These algorithms have a very transparent, easy to program structure. For finite fields of large characteristic p, so that exhaustive search through Zp
Computations in finite fields
root-finding
factorization of polynomials
probabilistic algorithms
In this paper, we pursue the use of probalistic (randomized) algorithms in VLSI architectures, in order to reduce the amount of computation, and, correspondingly, the time of computation as well as chip area. As a cas...
详细信息
In this paper, we pursue the use of probalistic (randomized) algorithms in VLSI architectures, in order to reduce the amount of computation, and, correspondingly, the time of computation as well as chip area. As a case example, we propose two VLSI solutions to the well-known problem of the nearest pair of points in computational geometry. These implementations are based on Rabin's and Weide's probabilistic algorithms. The chip area and time of computation which result are each O( n ). This is a marked improvement over both the straightforward deterministic approach (leading to an O( n 2 ) computational time) and the deterministic algorithms known as being the best (leading to O( n log n )computational time). In suggesting a VLSI solution to the nearest-pair problem, we introduce two new systolic structures, a systolic grouper and a systolic minimum-distance processor. We also make use of a new class of systolic arrays introduced earlier, probabilistic systolic arrays.
This paper presents an original hybrid approach to solve the Capacitated Vehicle Routing Problem (CVRP). The approach combines a probabilistic Algorithm with Constraint Programming (CP) and Lagrangian Relaxation (LR)....
详细信息
This paper presents an original hybrid approach to solve the Capacitated Vehicle Routing Problem (CVRP). The approach combines a probabilistic Algorithm with Constraint Programming (CP) and Lagrangian Relaxation (LR). After introducing the CVRP and reviewing the existing literature on the topic, the paper proposes an approach based on a probabilistic Variable Neighbourhood Search (VNS) algorithm. Given a CVRP instance, this algorithm uses a randomized version of the classical Clarke and Wright Savings constructive heuristic to generate a starting solution. This starting solution is then improved through a local search process which combines: (a) LR to optimise each individual route, and (b) CP to quickly verify the feasibility of new proposed solutions. The efficiency of our approach is analysed after testing some well-known CVRP benchmarks. Benefits of our hybrid approach over already existing approaches are also discussed. In particular, the potential flexibility of our methodology is highlighted.
Two sets of investigators have recently discovered polynomial time probabilistic algorithms with small error probability for a problem in NP conjoined with co-NP. The discovery raises the question whether probabilist...
详细信息
Two sets of investigators have recently discovered polynomial time probabilistic algorithms with small error probability for a problem in NP conjoined with co-NP. The discovery raises the question whether probabilistic algorithms perhaps are more powerful than nondeterministic ones. More specifically, a question arises about the possibilities for discovering a polynomial time probabilistic algorithm with small error probability for some NP-hard problem. Through an analysis that draws from the work that led to the recent discovery, it is concluded that all NP-hard optimization problems have some probabilistic algorithms with small error bounds.
Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least 1/2 log * n - 2 rounds,...
详细信息
Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least 1/2 log * n - 2 rounds, otherwise the probability that all processors are colored legally is less than 1/2. A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin [Inform. and Control, 70 (1986), pp. 32-53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331-335].
作者：
REISCHUK, RUniv Bielefeld
Fakultaet fuer Mathematik Bielefeld West Ger Univ Bielefeld Fakultaet fuer Mathematik Bielefeld West Ger
probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes wit...
详细信息
probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes with high probability in constant time and the sorting tree in time O(logn)
暂无评论