摘要:

AbstractThe Lovász Local Lemma is a remarkable sieve method to prove theexistenceof certain structures without supplying any efficient way offindingthese structures. In this article we convert some of the applications of the Local Lemma into polynomial time sequential algorithms (at the cost of a weaker constant factor in the “exponent”). Our main example is the following: assume that in an n‐uniform hypergraph every hyperedge intersects at most 2n/48other hyperedges, then there is a polynomial time algorithm that finds a two‐coloring of the points such thatnohyperedge is monoc

ISSN:1042-9832    

DOI:10.1002/rsa.3240020402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractThe Lovasz Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck recently has found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. His method does not seem to be parallelizable. Here we modify his technique and achieve an algorithmic version that can be parallelized, thus obtaining deterministicNClalgorithms for several interesting algorithmic problems.

ISSN:1042-9832    

DOI:10.1002/rsa.3240020403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractWe analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of sizem.We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction ofm.New results are obtained on them→ ∞ asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher‐order asymptotics follow from WKB expan

ISSN:1042-9832    

DOI:10.1002/rsa.3240020404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractLetG(n, M) be a graph chosen at random from the family of all labelled graphs withnvertices andM(n) = 0.5n+s(n) edges, wheres3(n)n−2→∞ buts(n)= o(n). We find the limit distribution of the length of shortest cycle contained in the largest component ofG(n, M), as well as of the longest cycle outside it. We also describe the block structure ofG(n, M) and derive from this result the limit probability thatG(n, M) contains a cycle with a diagonal. Finally, we show that the probability tending to 1 asn‐→∞ the length of the longest cycle inG(n, M) is of the o

ISSN:1042-9832    

DOI:10.1002/rsa.3240020405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240020401

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY