b'@techreport{BrodalChaudhuriRadhakrishnan96,'b'\nTITLE = {The randomized complexity of maintaining the minimum},\nAUTHOR = {Brodal, Gerth St{\\o}lting and Chaudhuri, Shiva and Radhakrishnan, Jaikumar},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1996-1-014},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1996},\nDATE = {1996},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'