We pro,ide an analysis of a recent path planning method which uses probabilistic roadmaps, This method has proven very successful in practice, but the theoretical understanding of its performance is still limited, Ass...
详细信息
We pro,ide an analysis of a recent path planning method which uses probabilistic roadmaps, This method has proven very successful in practice, but the theoretical understanding of its performance is still limited, Assuming that a path;exists Between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b on: 1) the length of gamma;2) the distance function of gamma from the obstacles;3) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly an local irregularities of the configuration space, as was the case with previous analysis. These results are illustrated with a simple but illuminating example. In this example, we provide estimates for N, the principal parameter of the method, in order to achieve failure probability within prescribed hounds, We also compare, through this example. the different approaches to the analysis of the planning method.
We give a distributed randomized algorithm for graph edge colouring. Let G be a Delta-regular graph with n nodes. Here we prove: If epsilon>0 is fixed and Delta much greater than log n, the algorithm almost always ...
详细信息
We give a distributed randomized algorithm for graph edge colouring. Let G be a Delta-regular graph with n nodes. Here we prove: If epsilon>0 is fixed and Delta much greater than log n, the algorithm almost always colours G with (1 + epsilon)Delta colours in time O(log n). If s>0 is fixed, there exists a positive constant k such that if Delta much greater than log(k) n, the algorithm almost always colours G with Delta + Delta/ log(s) n colours in time O(log n + log(s) n log log n). By "almost always" we mean that the algorithm may either use more than the claimed number of colours or run longer than the claimed time, but that the probability that either of these sorts of failure occurs can be made arbitrarily close to 0. The algorithm is based on the nibble method, a probabilistic strategy introduced by Vojtech Rodl. The analysis makes use of a powerful large deviation inequality for functions of independent random variables. (C) 1998-Elsevier Science B.V. All rights reserved.
We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 ... 2(w)-1 in O(n log log n) time for arbitrary w greater than or equal to log n, a significant improvement over the bound o...
详细信息
We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 ... 2(w)-1 in O(n log log n) time for arbitrary w greater than or equal to log n, a significant improvement over the bound of O(n root log n) achieved by the fusion trees of Fredman and Willard. Provided that w greater than or equal to (log n)(2+epsilon) for some fixed epsilon> 0. the sorting can even be accomplished in linear expected time with a randomized algorithm. Both of our algorithms parallelize without loss on a unit-cost PRAM with a word length of w bits. The first one yields an algorithm that uses O(log n) time and O(n log log n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w greater than or equal to (log n)(2+epsilon) for some fixed epsilon > 0. Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting of multiple-precision integers represented in several words. (C) 1998 Academic Press.
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the maximum arrival r...
详细信息
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the maximum arrival rate for which the protocol is stable and the expected delay of a request from arrival to service. Known solutions are either unstable for any constant injection rate or have at least polynomial (in the number of contenders) expected delay. Our main contribution is a protocol that is stable for a constant injection rate, while achieving logarithmic expected delay. We extend our results to the case of multiple servers, with each request being targeted for a specific server. This is related to the optically connected parallel computer (or OCPC) model. Finally, we prove a lower bound showing that long delays are inevitable in a class of protocols including backoff-style protocols, if the arrival rate is large enough (but still smaller than 1).
We present MULTI, a symmetric, distributed, randomized algorithm that, with probability one, schedules multiparty interactions in a strongly fair manner. To our knowledge, MULTI is the first algorithm for strong inter...
详细信息
We present MULTI, a symmetric, distributed, randomized algorithm that, with probability one, schedules multiparty interactions in a strongly fair manner. To our knowledge, MULTI is the first algorithm for strong interaction fairness to appear in the literature. Moreover, the expected time taken by MULTI to establish an interaction is a constant not depending on the total number of processes in the system. In this sense, MULTI guarantees real-time response. MULTI makes no assumptions (other than boundedness) about the time it takes processes to communicate. It, thus, offers an appealing tonic to the impossibility results of Tsay and Bagrodia, and Joung concerning strong interaction fairness in an environment, shared-memory, or message-passing, in which processes are deterministic and the communication time is nonnegligible, Because strong interaction fairness is as strong a fairness condition that one might actually want to impose in practice, our results indicate that randomization may also prove fruitful for other notions of fairness lacking deterministic realizations and requiring real-time response.
We prove that any depth-3 circuit with MOD m gates of unbounded fan-in on the lowest level, AND gates on the second, and a weighted threshold gate on the top needs either exponential size or exponential weights to com...
详细信息
We prove that any depth-3 circuit with MOD m gates of unbounded fan-in on the lowest level, AND gates on the second, and a weighted threshold gate on the top needs either exponential size or exponential weights to compute the inner product of two vectors of length n over GF(2). In contrast, with n AND gates at the bottom and n single MOD 2 gate at the top one can compute the inner product function. The lower-bound proof does not use any monotonicity or uniformity assumptions, also works for composite m's, and all of the gates have unbounded fan-in. Our main lemma asserts that functions, computed by depth-2 AND-MOD m circuits have low probabilistic communication complexity. (C) 1998 Elsevier Science B.V. All rights reserved.
We consider the problem of sorting n numbers that contain only k distinct values. We present a randomized arbitrary CRCW PRAM algorithm that runs in O(log n) time using (n log k)/log n processors. The same algorithm r...
详细信息
We consider the problem of sorting n numbers that contain only k distinct values. We present a randomized arbitrary CRCW PRAM algorithm that runs in O(log n) time using (n log k)/log n processors. The same algorithm runs in O((log n)/log log n) time with a total work of O(n (log k)(1+epsilon)) for any fixed epsilon > 0. All the stated bounds hold with high probability. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
This note gives a short proof of a sampling lemma used by Karger, Klein, and Tajan in the analysis of their randomized linear-time algorithm for minimum spanning trees. (C) 1998 Published by Elsevier Science B.V. All ...
详细信息
This note gives a short proof of a sampling lemma used by Karger, Klein, and Tajan in the analysis of their randomized linear-time algorithm for minimum spanning trees. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
We obtain bounds for the distribution of the number of comparisons needed by Hoare's randomized selection algorithm FIND and give a new proof for Grubel and Rosler's (1996) result on the convergence of this di...
详细信息
We obtain bounds for the distribution of the number of comparisons needed by Hoare's randomized selection algorithm FIND and give a new proof for Grubel and Rosler's (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results fur the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9 about 4.72 x n comparisons to find the median of S.
This paper considers the problem of scheduling dynamic parallel computations to achieve linear speedup without using significantly more space per processor than that required for a single-processor execution. Utilizin...
详细信息
This paper considers the problem of scheduling dynamic parallel computations to achieve linear speedup without using significantly more space per processor than that required for a single-processor execution. Utilizing a new graph-theoretic model of multithreaded computation, execution efficiency is quantified by three important measures: T-1 is the time required for executing the computation on a 1 processor, T-infinity is the time required by an infinite number of processors, and S-1 is the space required to execute the computation on a 1 processor. A computation executed on P processors is time-efficient if the time is O(T-1/P + T-infinity), that is, it achieves linear speedup when P = O(T-1/T-infinity), and it is space-efficient if it uses O(S1P) total space, that is, the space per processor is within a constant factor of that required for a 1-processor execution. The first result derived from this model shows that there exist multithreaded computations such that no execution schedule can simultaneously achieve efficient time and efficient space. But by restricting attention to "strict" computations-those in which all arguments to a procedure must be available before the procedure can be invoked-much more positive results are obtainable. Specifically, for any strict multithreaded computation, a simple online algorithm can compute a schedule that is both time-efficient and space-efficient. Unfortunately, because the algorithm uses a global queue, the overhead of computing the schedule can be substantial. This problem is overcome by a decentralized algorithm that can compute and execute a P-processor schedule online in expected time O(T-1/P + T-infinity lg P) and worst-case space O(S1P lg P), including overhead costs.
暂无评论