Improved Approximation Algorithms for the Freeze-Tag Problem (2004)
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He, Joseph S. B. Mitchell
In the Freeze-Tag Problem, the objective is to awaken a set of asleep" robots, starting with only one awake" robot. A robot awakens a sleeping robot by moving to the sleeping robot's position. When a...
The Cost of Cache-Oblivious Searching (2004)
Michael A. Bender, Gerth Stlting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, ...
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log B N block transfers...