@techreport{BrodalChaudhuriRadhakrishnan96,
TITLE = {The randomized complexity of maintaining the minimum},
AUTHOR = {Brodal, Gerth St{\o}lting and Chaudhuri, Shiva and Radhakrishnan, Jaikumar},
LANGUAGE = {eng},
NUMBER = {MPI-I-1996-1-014},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1996},
DATE = {1996},
ABSTRACT = {The complexity of maintaining a set under the operations {\sf Insert}, {\sf Delete} and {\sf FindMin} is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost $t$ comparisons per {\sf Insert} and {\sf Delete} has expected cost at least $n/(e2^{2t})-1$ comparisons for {\sf FindMin}. If {\sf FindMin} 474 is replaced by a weaker operation, {\sf FindAny}, then it is shown that a randomized algorithm with constant expected cost per operation exists, but no deterministic algorithm. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}