present the first exact analysis of a linear probing hashing scheme with buckets of size b. From the generating function for the Robin Hood heuristic we obtain exact expressions for the cost of successful searches. Fo...
详细信息
present the first exact analysis of a linear probing hashing scheme with buckets of size b. From the generating function for the Robin Hood heuristic we obtain exact expressions for the cost of successful searches. For a full table, with the help of Singularity analysis, we find the asymptotic expansion of this cost up to O((bm)(-1)). We conclude with a new approach to study certain recurrences that involve truncated exponentials. A new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers is introduced. These numbers may prove helpful in studying recurrences involving truncated generating functions.
von Neumann [(1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12: 36-38] introduced a simple algorithm for generating independent unbiased random bits ...
详细信息
von Neumann [(1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12: 36-38] introduced a simple algorithm for generating independent unbiased random bits by tossing a (possibly) biased coin with unknown bias. While his algorithm fails to attain the entropy bound, Peres [(1992). Iterating von Neumann's procedure for extracting random bits. The Annals of Statistics 20(1): 590-597] showed that the entropy bound can be attained asymptotically by iterating von Neumann's algorithm. Let b(n, p) denote the expected number of unbiased bits generated when Peres' algorithm is applied to an input sequence consisting of the outcomes of n tosses of the coin with bias p. With p =1/2, the coin is unbiased and the input sequence consists of n unbiased bits, so that n - b(n, 1/2) may be referred to as the cost incurred by Peres' algorithm when not knowing p = 1/2 We show that lim(n ->infinity) log[n - b(n, 1/2)]/log n = theta = log[1 +root 5)/2] (where log is the logarithm to base 2), which together with limited numerical results suggests that n - b(n,1/2) may be a regularly varying sequence of index theta. (A positive sequence {L(n)} is said to be regularly varying of index theta if lim(n ->infinity) L(left perpendicular lambda n right perpendicular)/L(n) = lambda(theta) for lambda > 0, where left perpendicular x right perpendicular denotes the largest integer not exceeding x.) Some open problems on the asymptotic behavior of nh(p) - b(n, p) are briefly discussed where h(p) = -p log p - (1 - p) log(1 - p) denotes the Shannon entropy of a random bit with bias p.
In a broadcast packet-switching network, there is an infinite number of users sharing a common communication channel. If no central coordination is provided, packet collision will occur. The problem, then, involves ...
详细信息
In a broadcast packet-switching network, there is an infinite number of users sharing a common communication channel. If no central coordination is provided, packet collision will occur. The problem, then, involves finding an efficient algorithm for retransmitting conflicting packets. In recent years, conflict resolution algorithms have been created. The basic concept is to solve each conflict through so-called conflict resolution intervals. In such an interval, a conflict of multiplicity n is divided into conflicts of smaller multiplicity until n conflicts of multiplicity one occur. The division can be made on the basis of a random variable or on the basis of the time at which a user became active. While early analyses of these algorithms solved the recurrence numerically only, for the Capetanakis-Tsybakov-Mikhailov algorithm, a closed-form solution and asymptotic approximation of the equation have been presented. A closed form expression is given for the throughput of the Gallager-Tsybakov-Mikhailov algorithm.
QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosi...
详细信息
QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosing pivot elements. In order to obtain the result we present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort. We show that for every input the expected number of comparisons is at most for the in-place variant. If we allow n extra bits, then we can lower the bound to . Thus, spending n extra bits we can save more that 0.96n comparisons if n is large enough. Both estimates improve the previously known results. Moreover, our non-in-place variant does essentially use the same number of comparisons as index based Heapsort variants and Relaxed-Weak-Heapsort which use comparisons in the worst case. However, index based Heapsort variants and Relaxed-Weak-Heapsort require extra bits whereas we need n bits only. Our theoretical results are upper bounds and valid for every input. Our computer experiments show that the gap between our bounds and the actual values on random inputs is small. Moreover, the computer experiments establish QuickHeapsort as competitive with Quicksort in terms of running time.
Though the behaviors of mergesort algorithms are basically known, the periodicity phenomena encountered in their analyses are not easy to deal with. In this paper closed-form expressions for the necessary number of co...
详细信息
Though the behaviors of mergesort algorithms are basically known, the periodicity phenomena encountered in their analyses are not easy to deal with. In this paper closed-form expressions for the necessary number of comparisons are derived for the bottom-up algorithm, which adequately describe its periodic behavior. This allows us, among other things, to compare the top-down and bottom-up mergesort algorithms.
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard probl...
详细信息
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard problems are rare. This paper contributes a theoretical understanding of EAs on the NP-hard multiprocessor scheduling problem. The worst-case bound on the (1+1)EA for the multiprocessor scheduling problem and a worst-case example are presented. It is proved that the (1+1)EA on problem achieves an approximation ratio of in expected time . Finally, the theoretical analysis on three selected instances of the multiprocessor scheduling problem shows that EAs outperform local search algorithms on these instances.
We analyze multiple Quickselect (MQS), a variant of Quicksort designed to search for several order statistics simultaneously. We show that, when p is an integer fixed with respect to n, the size of the data set, MQS r...
详细信息
We analyze multiple Quickselect (MQS), a variant of Quicksort designed to search for several order statistics simultaneously. We show that, when p is an integer fixed with respect to n, the size of the data set, MQS requires an average of (2H(p) + 1)n - 8p1nn + 0(1) comparisons to find p order statistics, where H-p is the pth harmonic number.
The stochastic matching problem with applications in online dating and kidney exchange was introduced by Chen et al. (2009) [1] together with a simple greedy strategy. They proved it is a 4-approximation, but conjectu...
详细信息
The stochastic matching problem with applications in online dating and kidney exchange was introduced by Chen et al. (2009) [1] together with a simple greedy strategy. They proved it is a 4-approximation, but conjectured that the greedy algorithm is in fact a 2-approximation. In this paper we confirm this hypothesis. (C) 2011 Elsevier B.V. All rights reserved.
Determinization and complementation are two fundamental problems in automata theory. Very recently, Piterman improved Safra's determinization and, presented a new construction which produces parity automata with a...
详细信息
Determinization and complementation are two fundamental problems in automata theory. Very recently, Piterman improved Safra's determinization and, presented a new construction which produces parity automata with a smaller size. We give a tighter analysis on that determinization construction and show that the number of states of the resulting deterministic automaton is bounded by 2n(n!)(2) instead of 2n!n(n). (C) 2009 Elsevier B.V. All rights reserved.
作者：
Durand, MINRIA
Algorithms Project F-78153 Le Chesnay France
Jon Bentley and Douglas McIlroy have implemented a fast quicksort for the C standard library in 1993. We consider here the average-case complexity in terms of number of comparisons of this algorithm, and give its asym...
详细信息
Jon Bentley and Douglas McIlroy have implemented a fast quicksort for the C standard library in 1993. We consider here the average-case complexity in terms of number of comparisons of this algorithm, and give its asymptotic expansion up to the constant order. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论