Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization (2007)
He, Simai, Luo, Zhi-Quan, Nie, Jiawang, Zhang, Shuzhong
In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic...
Improved Approximation Algorithms for the Freeze-Tag Problem (2004)
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He
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...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...