Results 1 to 10 of about 380,355 (349)
A probabilistic analysis of some tree algorithms [PDF]
The Annals of Applied Probability, 2005 In this paper a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily without resorting to the usual complex analysis techniques.
Hanène Mohamed, Philippe Robert
semanticscholar +8 more sources
A Statistical Analysis of Probabilistic Counting Algorithms [PDF]
Scandinavian Journal of Statistics, 2011 Abstract. This article considers the problem of cardinality estimation in data stream applications. We present a statistical analysis of probabilistic counting algorithms, focusing on two techniques that use pseudo‐random variates to form low‐dimensional data sketches.
Peter Clifford, Ioana A. Cosma
semanticscholar +7 more sources
Probabilistic analysis and algorithms for reconfiguration of memory arrays [PDF]
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992 Reconfiguration of memory arrays with spare rows and columns has been shown to be an NP-complete problem. An analysis of average-case time complexities of several existing heuristics is presented, as well as a provably average-case polynomial-time algorithm for reconfiguration of memories with spare rows and columns.
Wei Shi, W.K. Fuchs
semanticscholar +5 more sources
Probabilistic Analysis of Algorithms [PDF]
Texts and Monographs in Computer Science, 1987 Publisher Summary This chapter explores the probabilistic analysis of algorithms that has become an active research area. It reviews some representative results that are known for problems defined in the Euclidean plane. The chapter examines the fertile area of optimization problems defined on graphs and networks and presents a short digression on ...
A. H. G. Rinnooy Kan, Leen Stougie
semanticscholar +8 more sources
Probabilistic analysis of some distributed algorithms [PDF]
Random Structures & Algorithms, 1990 AbstractIn this paper we analyze: (i) a storage allocation algorithm (D.E. Knuth, The Art of Computer Programming‐Vol. I, Addison‐Wesley, Reading, MA, 1969, Ex. 2.2.2.13) which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well‐known banker algorithm which plays a fundamental role in parallel ...
Louchard, Guy, Schott, René
semanticscholar +6 more sources
Probabilistic analysis of a network resource allocation algorithm [PDF]
Information and Control, 1986 Summary: A distributed algorithm is presented, for allocating a large number of identical resources (such as airline tickets) to requests which can arrive anywhere in a distributed network. Resources, once allocated, are never returned. The algorithm searches sequentially, exhausting certain neighborhoods of the request origin before proceeding to ...
Nancy Lynch +3 more
openalex +3 more sources
On Probabilistic Analysis of a Coalesced Hashing Algorithm [PDF]
The Annals of Probability, 1987 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boris Pittel
openalex +4 more sources
Probabilistic Robustness Analysis—Risks, Complexity, and Algorithms [PDF]
SIAM Journal on Control and Optimization, 2008 It is becoming increasingly apparent that probabilistic approaches can overcome conservatism and computational complexity of the classical worst-case deterministic framework and may lead to designs that are actually safer. In this paper we argue that a comprehensive probabilistic robustness analysis requires a detailed evaluation of the robustness ...
Xinjia Chen, Kemin Zhou, J.L. Aravena
openalex +4 more sources
A probabilistic analysis of a leader election algorithm [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 A leader election algorithm is an elimination process that divides recursively into tow subgroups an initial group of n items, eliminates one subgroup and continues the procedure until a subgroup is of size 1. In this paper the biased case is analyzed. We are interested in the cost of the algorithm e. the number of operations needed until the algorithm
Hanène Mohamed
openalex +7 more sources
Probabilistic Analysis of Network Flow Algorithms
Mathematics of Operations Research, 1993 This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability.
Rajeev Motwani +2 more
openaire +4 more sources