A method for obtaining randomized algorithms with small tail probabilities

被引：15

作者：

Alt, H

Guibas, L

Mehlhorn, K

Karp, R

Wigderson, A

机构：

[1] STANFORD UNIV,STANFORD,CA 94305

[2] DIGITAL EQUIPMENT CORP,SYST RES CTR,PALO ALTO,CA 94301

[3] UNIV SAARLAND,MAX PLANCK INST INFORMAT,D-6600 SAARBRUCKEN,GERMANY

[4] UNIV SAARLAND,FACHBEREICH INFORMAT,D-6600 SAARBRUCKEN,GERMANY

[5] INT COMP SCI INST,BERKELEY,CA 94704

[6] UNIV CALIF BERKELEY,BERKELEY,CA 94720

[7] HEBREW UNIV JERUSALEM,DEPT COMP SCI,IL-91905 JERUSALEM,ISRAEL

[8] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 07974

来源：

关键词：

Las Vegas algorithms; randomized algorithm; tail probability;

D O I：

10.1007/BF01940879

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.

引用

页码：543 / 547

页数：5